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

Intuitionwhy one running sum is enough

Every candidate has exactly k elements, so its average is at least threshold exactly when its sum is at least k multiplied by threshold. Comparing sums avoids division, floating point values, and any ambiguity around averages that are not whole numbers.

The first length-k subarray requires k additions. After that, the next window differs in only two places: it loses the element at the old left edge and gains the next element at the right edge. Keep the current sum, remove arr[i - k], add arr[i], and each new window is ready in constant time instead of being summed from scratch.

Approach

1. 1Compute target as k multiplied by threshold, because the average test sum / k >= threshold is equivalent to sum >= target and this avoids division entirely.
2. 2Add the first k elements to sum, because the loop that slides the window cannot create the first window by removing an element from a previous one.
3. 3Count the first window if sum >= target, because it is a valid candidate that must be checked before any rightward slide.
4. 4For each index i from k through n - 1, add arr[i] and remove arr[i - k], because those are exactly the entering and leaving values when the window shifts right by one.
5. 5Check the updated sum and increment count when it reaches target, because each update represents one new contiguous subarray of length k.
6. 6Return count after all windows have been checked, because there are n - k + 1 candidates and the first one plus every slide accounts for each of them exactly once.

Complexityone pass after one initial window

Annotated solutionC++ · fixed-size sliding window · constant extra space

#include <vector>

using namespace std;

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int n = arr.size();
        int target = k * threshold;
        int sum = 0;

        for (int i = 0; i < k; ++i) {
            sum += arr[i];
        }

        int count = (sum >= target) ? 1 : 0;

        for (int i = k; i < n; ++i) {
            sum += arr[i] - arr[i - k];
            if (sum >= target) {
                ++count;
            }
        }

        return count;
    }
};

The expression sum += arr[i] - arr[i - k] is the central line. At the start of an iteration, sum belongs to the window ending at i - 1. Removing arr[i - k] discards its old first element, and adding arr[i] creates the window ending at i. The count check comes after both updates, so it evaluates the new window rather than the previous one.

The prefix-sum alternativea different arrangement that spends linear extra space

A prefix-sum array can answer any length-k window sum as prefix[i + k] - prefix[i]. This is still O(n) time, but it stores n + 1 cumulative sums instead of reusing one running sum. It is a reasonable choice when the same array needs many later range-sum queries, but for this one-pass task it buys no speed and costs O(n) extra space.

#include <vector>

using namespace std;

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int n = arr.size();
        int target = k * threshold;
        vector<int> prefix(n + 1, 0);

        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + arr[i];
        }

        int count = 0;
        for (int start = 0; start + k <= n; ++start) {
            int sum = prefix[start + k] - prefix[start];
            if (sum >= target) {
                ++count;
            }
        }

        return count;
    }
};

Common mistakesthree lines that change the result or the bound