Problem Description

Given an array of integers arr, an integer k, and an integer threshold, your task is to count the number of contiguous subarrays of size k whose average value is greater than or equal to threshold.

• You may only use each element of arr once per subarray window (i.e., subarrays must be contiguous and non-overlapping).
• Return the count of such subarrays.
• The solution must be efficient for large arrays (up to 10⁵ elements).

Example:
Input: arr = [2,1,3,4,1,2,3,2], k = 3, threshold = 3
Output: 3

Thought Process

The problem asks us to count all contiguous subarrays of length k whose average is at least threshold. A straightforward (brute-force) approach would be to check every possible subarray of length k, compute its average, and count the ones that meet the criterion.

However, this brute-force solution would require us to sum up k elements for each subarray, leading to a time complexity of O(n*k), which is not efficient for large arrays.

To optimize, we observe that each subarray of length k overlaps heavily with the next one. By using a sliding window technique, we can efficiently compute the sum of each subarray in O(1) time after the first window by subtracting the element that leaves the window and adding the new element that enters.

Solution Approach

We use the sliding window approach to efficiently compute the sum of every subarray of size k and check if its average meets the threshold.

1. Initialize: Start by computing the sum of the first k elements of arr. This sum represents the first window.
2. Iterate with Sliding Window: For each subsequent subarray, subtract the element that's leaving the window and add the new element that's entering the window. This allows us to update the window sum in constant time.
3. Check Average: For each window, check if the average (window sum divided by k) is at least threshold. If it is, increment the count.
4. Return Count: After processing all possible windows, return the total count.

Why use window sum instead of average? Since we only care about whether the average is at least threshold, we can avoid floating-point division by comparing window_sum directly to threshold * k.

Example Walkthrough

Let's walk through the example:
arr = [2,1,3,4,1,2,3,2], k = 3, threshold = 3

1. First window (indices 0-2): [2,1,3] → sum = 6, average = 2
   6 < 9 (since threshold * k = 3 * 3 = 9), so not counted.
2. Second window (indices 1-3): [1,3,4] → sum = 8, average ≈ 2.67
   8 < 9, not counted.
3. Third window (indices 2-4): [3,4,1] → sum = 8, average ≈ 2.67
   8 < 9, not counted.
4. Fourth window (indices 3-5): [4,1,2] → sum = 7, average ≈ 2.33
   7 < 9, not counted.
5. Fifth window (indices 4-6): [1,2,3] → sum = 6, average = 2
   6 < 9, not counted.
6. Sixth window (indices 5-7): [2,3,2] → sum = 7, average ≈ 2.33
   7 < 9, not counted.

Oops! This example doesn't have any windows with average ≥ 3. Let's try another example:
arr = [1,4,2,5,6], k = 2, threshold = 4

• [1,4] → sum=5, average=2.5 → 5 < 8, not counted
• [4,2] → sum=6, average=3 → 6 < 8, not counted
• [2,5] → sum=7, average=3.5 → 7 < 8, not counted
• [5,6] → sum=11, average=5.5 → 11 ≥ 8, counted

Only the last window meets the criterion, so the answer is 1.

Time and Space Complexity

• Brute-force:
  • Time Complexity: O(n*k), since for each of the n-k+1 subarrays, you sum k elements.
  • Space Complexity: O(1), since only counters and temporary sums are needed.
• Optimized (Sliding Window):
  • Time Complexity: O(n), since each element is added and subtracted at most once as the window slides.
  • Space Complexity: O(1), since only a few variables are used for counting and summing.

Summary

The key insight for this problem is to use a sliding window to efficiently compute the sum of each subarray of size k in constant time, rather than recomputing sums from scratch. This reduces the time complexity from O(n*k) to O(n), making the solution suitable for large arrays. By comparing the window sum to threshold * k, we avoid division and floating-point issues. This approach is elegant, efficient, and easy to implement.

Code Implementation

class Solution:
    def numOfSubarrays(self, arr, k, threshold):
        count = 0
        window_sum = sum(arr[:k])
        target = threshold * k
        if window_sum >= target:
            count += 1
        for i in range(k, len(arr)):
            window_sum += arr[i] - arr[i - k]
            if window_sum >= target:
                count += 1
        return count
      

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int count = 0;
        int window_sum = 0;
        int target = threshold * k;
        for (int i = 0; i < k; ++i) {
            window_sum += arr[i];
        }
        if (window_sum >= target) count++;
        for (int i = k; i < arr.size(); ++i) {
            window_sum += arr[i] - arr[i - k];
            if (window_sum >= target) count++;
        }
        return count;
    }
};
      

class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int count = 0;
        int windowSum = 0;
        int target = threshold * k;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        if (windowSum >= target) count++;
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k];
            if (windowSum >= target) count++;
        }
        return count;
    }
}
      

var numOfSubarrays = function(arr, k, threshold) {
    let count = 0;
    let windowSum = 0;
    let target = threshold * k;
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    if (windowSum >= target) count++;
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        if (windowSum >= target) count++;
    }
    return count;
};