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

Problem Overview: You are given an integer array arr, a window size k, and a threshold. Count how many contiguous subarrays of length k have an average greater than or equal to the threshold. Since the subarray size is fixed, the task reduces to efficiently computing the sum of every window of length k and checking whether sum / k >= threshold.

Approach 1: Brute Force (Time: O(n * k), Space: O(1))

The straightforward method iterates over every possible subarray of length k. For each starting index, compute the sum of the next k elements using a loop, calculate the average, and compare it with the threshold. If the condition holds, increment the result counter. This approach uses no extra memory beyond a few variables, but repeatedly recalculates sums for overlapping windows. When n is large, recomputing each window from scratch becomes inefficient because each element is processed up to k times.

Approach 2: Sliding Window (Time: O(n), Space: O(1))

The optimal approach uses a Sliding Window over the Array. Instead of recomputing sums for each subarray, maintain the sum of the current window of size k. First compute the sum of the initial k elements. Then move the window one step to the right by subtracting the element leaving the window and adding the new element entering the window. Each shift updates the sum in constant time. Check whether windowSum >= k * threshold instead of computing division; this avoids floating-point operations and simplifies comparison.

Because each element enters and leaves the window exactly once, the total work is linear in the size of the array. The algorithm uses only a few variables to track the running sum and the result count, so the extra space remains constant. This technique appears frequently in problems where a fixed-size window moves across an array.

Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize repeated work in overlapping subarrays and replace it with a rolling sum update. Mentioning the brute force approach first demonstrates understanding of the problem, but switching to the sliding window optimization shows algorithmic maturity and familiarity with common patterns like Sliding Window on arrays.