#1343

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

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

Given an array, find the number of sub-arrays of size k with an average greater than or equal to a given threshold.

Problem Statement

You are given an integer array arr and two integers k and threshold. Your task is to return the number of sub-arrays of size k that have an average greater than or equal to the given threshold.

A sub-array is a contiguous part of the array. For instance, for the array [2,2,2,2,5,5,5,8] with k = 3 and threshold = 4, sub-arrays like [2, 5, 5] have an average of 4, which meets the threshold condition.

Examples

Example 1

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4

Output: 3

Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Example 2

Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5

Output: 6

The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Constraints

1 <= arr.length <= 105
1 <= arr[i] <= 104
1 <= k <= arr.length
0 <= threshold <= 104

Solution Approach

Sliding Window with Running Sum

Start by calculating the sum of the first k elements. Then slide the window across the array. For each new element added to the window, subtract the element that is no longer part of the window. This approach allows for efficient computation of averages in O(1) time per sub-array.

Efficiency Considerations

The sliding window technique reduces the time complexity from O(k * n) to O(n). By updating the sum incrementally, we avoid recalculating the sum of every sub-array from scratch, ensuring the solution scales efficiently with large inputs.

Edge Case Handling

Ensure that the case where k is equal to the length of the array is handled. Also, consider the case where all sub-arrays have averages less than the threshold, resulting in a count of zero.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because we process each element once while sliding the window. Space complexity is O(1) since we only need variables to track the current sum and the count of valid sub-arrays, regardless of input size.

What Interviewers Usually Probe

Can the candidate implement the sliding window approach efficiently?
Does the candidate handle edge cases such as when k equals the array length?
How well does the candidate explain their approach, especially with respect to avoiding recalculating sums repeatedly?

Common Pitfalls or Variants

Common pitfalls

Incorrectly recalculating the sum for every sub-array from scratch instead of updating it incrementally.
Missing edge cases like when the size of the sub-array k equals the array length.
Not properly handling the condition where no sub-arrays meet the threshold, leading to returning an incorrect count.

Follow-up variants

How would this approach change if we need to track sub-arrays of variable sizes?
What if instead of an average, the threshold were a sum condition?
How could this solution be adapted for multidimensional arrays or matrices?

FAQ

How do I optimize this problem using the sliding window pattern?

By maintaining a running sum of the current window, you can efficiently update the sum as the window slides across the array. This eliminates the need to recalculate sums from scratch.

What is the time complexity of this approach?

The time complexity is O(n) because we process each element exactly once while sliding the window. The space complexity is O(1), as we only need a few variables to track the sum and valid sub-arrays.

What edge cases should I consider for this problem?

Edge cases include when k is equal to the array length, when no sub-arrays meet the threshold, and when the array contains repeated values.

Can I use this approach for larger arrays?

Yes, the sliding window approach is highly efficient and works well even for arrays with lengths up to 100,000, as it reduces the time complexity to O(n).

How does the threshold affect the number of valid sub-arrays?

A higher threshold will reduce the number of valid sub-arrays, as fewer sub-arrays will meet the average condition. Conversely, a lower threshold may result in more valid sub-arrays.

terminal

Solution

Solution 1: Sliding Window

We can multiply `threshold` by $k$, so that we can directly compare the sum within the window with `threshold`.

1

2

3

4

5

6

7

8

9

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        threshold *= k
        s = sum(arr[:k])
        ans = int(s >= threshold)
        for i in range(k, len(arr)):
            s += arr[i] - arr[i - k]
            ans += int(s >= threshold)
        return ans

Continue Practicing

#1423 maximum points you can obtain from cards #1425 constrained subsequence sum #1248 count number of nice subarrays