Problem Description

You are given an array of integers arr and two integers k and threshold. Your task is to find how many contiguous sub-arrays of exactly size k have an average value that is greater than or equal to threshold.

A sub-array is a contiguous portion of the original array. For example, if arr = [1, 2, 3, 4] and k = 2, the sub-arrays of size 2 would be [1, 2], [2, 3], and [3, 4].

To find the average of a sub-array, you sum all its elements and divide by k. If this average is greater than or equal to threshold, that sub-array counts toward your answer.

The solution uses a sliding window technique to efficiently calculate this. Instead of repeatedly calculating averages, it multiplies threshold by k at the beginning. This allows direct comparison of the window's sum with threshold * k, avoiding division operations.

The algorithm works by:

1. First calculating the sum of the initial window of size k
2. Sliding the window one position at a time by removing the leftmost element and adding the new rightmost element
3. Checking if each window's sum meets or exceeds threshold * k
4. Counting all windows that satisfy the condition

For example, with arr = [2, 2, 2, 2, 5, 5, 5, 8], k = 3, and threshold = 4:

• The sub-arrays of size 3 are: [2,2,2], [2,2,2], [2,2,5], [2,5,5], [5,5,5], [5,5,8]
• Their averages are: 2, 2, 3, 4, 5, 6
• Four of these (4, 5, 6) are >= 4, so the answer is 4

Intuition

The naive approach would be to check every possible sub-array of size k by calculating its sum and then dividing by k to get the average. However, this involves redundant calculations since consecutive windows overlap significantly.

Consider two consecutive windows: one starting at index i and another at index i+1. These windows share k-1 elements. When we move from the first window to the second, we're essentially removing one element from the left and adding one element from the right. This observation leads us to the sliding window technique.

Instead of recalculating the entire sum for each window, we can maintain a running sum and update it by:

• Subtracting the element that's leaving the window (the leftmost element of the previous window)
• Adding the element that's entering the window (the new rightmost element)

This reduces our work from O(k) per window to O(1) per window.

Another key insight is about the comparison with the threshold. The condition "average >= threshold" can be rewritten as "sum >= threshold * k". By multiplying the threshold by k once at the beginning, we avoid performing division for each window. This is both more efficient and avoids potential floating-point precision issues.

The pattern s += arr[i] - arr[i - k] elegantly captures the sliding window update: arr[i] is the new element entering the window, and arr[i - k] is the element leaving the window that's exactly k positions behind.

This approach transforms what could be an O(n * k) solution into an O(n) solution, where n is the length of the array.

Learn more about Sliding Window patterns.

Solution Approach

The solution implements a sliding window technique to efficiently count sub-arrays of size k with average greater than or equal to threshold.

Step 1: Transform the comparison

threshold *= k

We multiply threshold by k to transform the average comparison into a sum comparison. This allows us to check if sum >= threshold * k instead of sum/k >= threshold, avoiding division operations.

Step 2: Initialize the first window

s = sum(arr[:k])
ans = int(s >= threshold)

We calculate the sum of the first k elements to establish our initial window. The expression int(s >= threshold) converts the boolean result to 1 if the condition is met, or 0 otherwise. This counts whether the first window satisfies our requirement.

Step 3: Slide the window through the array

for i in range(k, len(arr)):
    s += arr[i] - arr[i - k]
    ans += int(s >= threshold)

Starting from index k, we slide the window one position at a time:

• arr[i] is the new element entering the window on the right
• arr[i - k] is the element leaving the window on the left
• The difference updates our running sum s in constant time

For each new window position, we check if the sum meets our threshold and increment the answer accordingly.

Time Complexity: O(n) where n is the length of the array. We visit each element exactly once after the initial window setup.

Space Complexity: O(1) as we only use a constant amount of extra space for variables s and ans.

The elegance of this solution lies in maintaining a running sum that's updated incrementally, rather than recalculating the entire sum for each window. This pattern is particularly useful for problems involving consecutive sub-arrays of fixed size.

Example Walkthrough

Let's walk through a small example with arr = [1, 3, 2, 6, 2], k = 3, and threshold = 3.

Step 1: Transform the threshold

• Original condition: average ≥ 3
• Multiply threshold by k: threshold = 3 * 3 = 9
• New condition: sum ≥ 9

Step 2: Initialize the first window

• First window: [1, 3, 2]
• Sum: s = 1 + 3 + 2 = 6
• Check: Is 6 ≥ 9? No
• ans = 0

Step 3: Slide the window

Window 2 (i = 3):

• Remove arr[0] = 1, add arr[3] = 6
• New window: [3, 2, 6]
• Update sum: s = 6 + 6 - 1 = 11
• Check: Is 11 ≥ 9? Yes
• ans = 0 + 1 = 1

Window 3 (i = 4):

• Remove arr[1] = 3, add arr[4] = 2
• New window: [2, 6, 2]
• Update sum: s = 11 + 2 - 3 = 10
• Check: Is 10 ≥ 9? Yes
• ans = 1 + 1 = 2

Result: 2 sub-arrays have average ≥ 3

The sliding window efficiently updates the sum by removing the element that exits (arr[i-k]) and adding the element that enters (arr[i]), avoiding recalculation of the entire window sum each time.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array arr. The algorithm first calculates the sum of the initial window of size k in O(k) time. Then it slides the window through the remaining n - k elements, performing constant time operations (adding one element and removing one element) for each position. Therefore, the total time is O(k) + O(n - k) = O(n).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space for variables s (to store the current window sum), ans (to count valid subarrays), and i (loop variable), regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Threshold Multiplication

Pitfall: When multiplying threshold * k, the result might exceed integer limits in some programming languages, especially when both values are large.

Example scenario:

• threshold = 10^9, k = 10^5
• threshold * k = 10^14 (may cause overflow in 32-bit integers)

Solution: Instead of multiplying the threshold, keep it as is and perform floating-point division:

# Instead of:
total_threshold = threshold * k
count = int(window_sum >= total_threshold)

# Use:
count = int(window_sum / k >= threshold)

Or use integer division with careful rounding:

count = int(window_sum >= threshold * k)  # Ensure using 64-bit integers

2. Off-by-One Error in Window Sliding

Pitfall: Incorrectly calculating which element to remove when sliding the window, often using arr[i - k + 1] or arr[i - k - 1] instead of the correct arr[i - k].

Example of wrong implementation:

# WRONG - removes wrong element
for i in range(k, len(arr)):
    window_sum += arr[i] - arr[i - k + 1]  # This is incorrect!

Solution: Visualize the window positions clearly:

• When i = k, we want to remove arr[0] and add arr[k]
• The element to remove is always at index i - k

3. Handling Edge Cases with Small Arrays

Pitfall: Not handling cases where the array length is less than k or exactly equals k.

Example scenario:

• arr = [1, 2], k = 3 - No valid subarray exists
• arr = [1, 2, 3], k = 3 - Only one subarray exists

Solution: Add validation at the beginning:

def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
    if len(arr) < k:
        return 0
  
    # Rest of the implementation...

4. Incorrect Initial Window Calculation

Pitfall: Starting the sliding window loop from the wrong index or miscounting the first window.

Example of wrong implementation:

# WRONG - doesn't check the first window
window_sum = sum(arr[:k])
count = 0  # Missing the check for first window!

for i in range(k, len(arr)):
    # ...

Solution: Always check if the first window meets the threshold:

window_sum = sum(arr[:k])
count = int(window_sum >= total_threshold)  # Check first window

5. Using Division Instead of Multiplication

Pitfall: Performing division in each iteration instead of transforming the comparison once.

Inefficient approach:

# INEFFICIENT - performs division in every iteration
for i in range(k, len(arr)):
    window_sum += arr[i] - arr[i - k]
    if window_sum / k >= threshold:  # Division in each iteration
        count += 1

Solution: Transform the comparison once at the beginning to avoid repeated divisions, which are computationally more expensive than comparisons.