Example
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).
Solution
Straightforward solution - consider all subarrays of size k and keep taking their sum in a “rolling” fashion. In the above example, let us initially take sum of the first 3 numbers = 2+2+2 = 6. This is the first subarray of size 3. Now, if we have to consider the second subarray of size 3, we simply have to do this: previous_sum + arr[4] - arr[0]. This gives us the sum arr[1]+arr[2]+arr[3]. We will continue doing this and consider the averages of all subarrays. Note that calculating average is easy once we have the sum as average = sum/k.
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
int sum=0, ans=0;
for (int i=0; i<arr.size(); i++) {
if (i<k) {
sum+=arr[i];
continue;
}
if (sum/k >= threshold)
ans++;
sum -= arr[i-k];
sum += arr[i];
}
if (sum/k >= threshold)
ans++;
return ans;
}
Time complexity: O(n)
Space complexity: O(1)