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

medium sliding window fixed window array

Problem

Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k whose average is greater than or equal to threshold. Because every window has the same length, an average meets the threshold exactly when the window's sum is at least k × threshold.

Inputarr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4

Output3

Windows [2,5,5], [5,5,5] and [5,5,8] have averages 4, 5 and 6; all other size-3 windows fall below 4.

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

Output6

The first six size-3 windows each average more than 5.

arr (comma-separated)

k (window size)

threshold

def num_of_subarrays(arr, k, threshold):
    target = k * threshold
    window = sum(arr[:k])
    count = 1 if window >= target else 0
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]
        if window >= target:
            count += 1
    return count

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

int numOfSubarrays(int[] arr, int k, int threshold) {
    int target = k * threshold;
    int window = 0;
    for (int i = 0; i < k; i++) window += arr[i];
    int count = window >= target ? 1 : 0;
    for (int i = k; i < arr.length; i++) {
        window += arr[i] - arr[i - k];
        if (window >= target) count++;
    }
    return count;
}

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

Explanation

The brute-force idea would recompute the sum of every length-k window from scratch, costing O(n·k). A fixed-size sliding window removes the repeated work by reusing one running sum.

First, turn the average test into an integer test. A window of size k has average ≥ threshold exactly when its sum ≥ k · threshold. We precompute target = k * threshold once and only ever compare sums against it, avoiding floating-point division.

We seed window with the sum of the first k elements and check it against target. That handles the very first window.

To advance to the next window we slide by one: add the incoming element arr[i] and subtract the outgoing element arr[i - k]. The sum updates in O(1), then we test it against target and bump count when it qualifies.

Each element is added once and removed once, so the whole scan is O(n) time and O(1) extra space. With arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4 we have target = 12; the windows with sum ≥ 12 are [2,5,5]=12, [5,5,5]=15 and [5,5,8]=18, giving the answer 3.

Time: O(n) Space: O(1)