Number of Sub-arrays of Size K and Average >= Threshold

Given an array of integers and two values k and threshold, you need to count how many contiguous sub-arrays of length k have an average value greater than or equal to threshold. That is the task in 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold. It is a clean application of the fixed-size sliding window, and it has a neat trick that sidesteps floating-point math entirely.

The sliding window approach

Because every sub-array you care about is exactly k elements wide, you can use a fixed-size sliding window. Compute the sum of the first k elements. Then slide the window one position to the right by subtracting the element that leaves and adding the element that enters. Each slide is O(1), and you only make one pass through the array.

At each position you need to check whether the average meets the threshold. Instead of dividing the sum by k and comparing to threshold, you can compare sum directly against k * threshold. Multiplying once up front is cheaper and avoids any floating-point precision issues. If sum >= k * threshold, that window qualifies.

The solution

def numOfSubarrays(arr, k, threshold):
    target = k * threshold
    window_sum = sum(arr[:k])
    count = int(window_sum >= target)

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        if window_sum >= target:
            count += 1

    return count

Step-by-step walkthrough

Let's trace through arr = [2, 1, 3, 4, 1, 2, 5, 3] with k = 3 and threshold = 3. The target sum is 3 * 3 = 9. Any window with a sum of 9 or more counts.

After sliding through all six window positions, only one window (indices 5 through 7 with sum 10) meets the threshold. The answer is 1.

Key insight: compare sums, not averages

Complexity analysis

Time: O(n). You make one pass through the array. Each element is added once and removed once.

Space: O(1). You only store the running sum, the target, and the count. No extra data structures are needed.

The building blocks

Fixed-size sliding window

The window is always exactly k elements wide. You compute the initial window sum, then slide forward by subtracting the departing element and adding the arriving element. This is the same template used in Maximum Average Subarray I and Find All Anagrams in a String. The only thing that changes between problems is what you track inside the window (a sum, a frequency map, a count).

Threshold comparison trick

Comparing sum >= k * threshold instead of sum / k >= threshold is a small algebraic rearrangement, but it matters in practice. It removes a division from every iteration and keeps everything in integer arithmetic. Watch for this pattern any time a problem asks you to compare an average against a fixed value.

Edge cases to watch for

• k equals the array length: There is only one window. The loop body never executes. The initial check on the first window handles this correctly.
• All elements below the threshold: No window will have a high enough sum. The count stays at zero. No special handling needed.
• All elements equal to the threshold: Every window has sum = k * threshold, so every window qualifies. The answer is n - k + 1.
• Large values of k: The window sum can grow large. In Python this is not an issue because integers have arbitrary precision, but in languages like C++ or Java you may want to use a long.

From understanding to recall

You have seen the fixed-size sliding window and the sum-vs-average trick. But under interview pressure, will you remember to multiply k * threshold up front instead of dividing at each step? Will you remember the off-by-one in arr[i - k]?

Spaced repetition drills these details into long-term memory. You revisit the problem at increasing intervals, each time writing the solution from scratch. After a few rounds, the template and the comparison trick become automatic.

Related posts

• Sliding Window Pattern
• Maximum Average Subarray I
• Max Consecutive Ones III