LeetCode Solutions Blog

Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

Number: 1445

Difficulty: Medium

Paid? No

Problem Description

Given an integer array and two integers k and threshold, return the number of sub-arrays of size k whose average is greater than or equal to threshold.

Key Insights

Use the sliding window technique to efficiently compute the sum of each subarray of size k.
Compare the sum directly against k * threshold to determine if the average meets the requirement.
Avoid recalculating the sum from scratch for each window by removing the element that is exiting and adding the new element coming in.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array. Space Complexity: O(1), constant additional space is used.

Solution

We apply a sliding window approach:

Calculate the sum of the first k elements.
Check if this sum is greater than or equal to k * threshold.
Slide the window across the array by subtracting the first element of the current window and adding the next element.
Increment a counter each time the sum of the window satisfies the condition.
Return the count of valid subarrays.

Code Solutions

# Python solution with line-by-line comments

def numOfSubarrays(arr, k, threshold):
    # Calculate the required sum based on the threshold and window size
    required_sum = k * threshold
    count = 0  # Initialize the counter for valid subarrays
    
    # Compute the sum of the first window of size k
    current_sum = sum(arr[:k])
    if current_sum >= required_sum:
        count += 1  # If condition is met, increment the count
    
    # Slide the window through the rest of the array
    for i in range(k, len(arr)):
        # Remove the element that is no longer in the window and add the new element
        current_sum += arr[i] - arr[i - k]
        if current_sum >= required_sum:
            count += 1  # Increment the count if the current window's sum meets the requirement
    
    return count

# Example usage:
# arr = [2,2,2,2,5,5,5,8]
# k = 3
# threshold = 4
# Expected output: 3
# print(numOfSubarrays(arr, k, threshold))