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

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

What is this problem about?

The Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold problem asks you to count subarrays of exactly length k whose average is ≥ threshold. This is equivalent to counting fixed-size windows with sum ≥ k * threshold. This coding problem is a clean fixed-size sliding window application.

Why is this asked in interviews?

Goldman Sachs, Amazon, and LinkedIn ask this as a standard fixed-size sliding window problem. It validates the efficient sliding window pattern — maintain a running sum and slide the window one step at a time instead of recomputing the sum from scratch. The array and sliding window interview pattern is directly demonstrated.

Algorithmic pattern used

Fixed-size sliding window. Compute the sum of the first k elements. Compare with k * threshold. Slide the window: for each subsequent position, add the new element and subtract the element leaving the window. Update count if window_sum >= k * threshold.

Example explanation

arr=[2,2,2,2,5,5,5,8], k=3, threshold=4. Required sum = 3*4=12.

• Window [2,2,2]: sum=6 < 12.
• Window [2,2,5]: sum=9 < 12.
• Window [2,5,5]: sum=12 ≥ 12. Count=1.
• Window [5,5,5]: sum=15 ≥ 12. Count=2.
• Window [5,5,8]: sum=18 ≥ 12. Count=3. Answer = 3.

Common mistakes candidates make

• Recomputing the sum from scratch for each window (O(nk) instead of O(n)).
• Comparing average to threshold as floats instead of using integer sum ≥ k*threshold.
• Off-by-one in the initial window setup.
• Not handling the case where the array has fewer than k elements.

Interview preparation tip

Fixed-size sliding window is the pattern for all "subarray of size k with aggregate condition" problems. The template: compute initial window, then for each step: add arr[i] and subtract arr[i-k], check condition. Never recompute from scratch. Comparing sum >= k * threshold instead of avg >= threshold avoids floating-point division. Practice all sliding window variants: min, max, sum, product, count. This pattern is fundamental for Goldman Sachs and LinkedIn quantitative interviews.