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

How it works

A small optimization: instead of dividing the sum by k for each comparison, we multiply the threshold by k once upfront. This converts the average check into a simple sum comparison, avoiding repeated division.

Steps

1. Multiply threshold by k to get the target sum.
2. Expand the window by adding elements from the right.
3. Once the window reaches size k:
   • Check if the current sum meets or exceeds the target.
   • Shrink the window from the left by removing the oldest element.
4. Return the count of valid subarrays.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Where n is the size of the array arr and k is the size of the sub-array.

Things to watch for

Integer Division Truncation

When computing sum / k in languages like Java, C++, or Go, integer division truncates toward zero. If the sum is 15 and k is 4, 15 / 4 equals 3, not 3.75. This can cause false negatives when the true average meets the threshold but the truncated result does not. Multiplying the threshold by k and comparing sums directly avoids this issue.

Recalculating the Window Sum

A common inefficiency is recalculating the sum for each window from scratch, leading to O(n*k) time complexity. The sliding window technique maintains a running sum, adding the new element and removing the old element in O(1) time per window.

Off-By-One Errors in Window Boundaries

When sliding the window, it is easy to make mistakes with index calculations. Ensure the window always contains exactly k elements. Common errors include starting the right pointer at the wrong index or incorrectly computing when to start shrinking the window from the left.

from typing import List

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        threshold *= k
        res = curSum = 0
        for R in range(len(arr)):
            curSum += arr[R]
            if R >= k - 1:
                res += curSum >= threshold
                curSum -= arr[R - k + 1]
        return res

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        threshold *= k;
        int res = 0, curSum = 0;

        for (int R = 0; R < arr.size(); R++) {
            curSum += arr[R];
            if (R >= k - 1) {
                if (curSum >= threshold) {
                    res++;
                }
                curSum -= arr[R - k + 1];
            }
        }
        return res;
    }
};