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

Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k and average greater than or equal to threshold.

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).

Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Constraints:

1 <= arr.length <= 10⁵
1 <= nums[i] <= 10⁴
0 <= k <= arr.length
0 <= threshold <= 10⁴

Solution 1 - Using sliding window technique, take the moving sum of window size of K and check if the average is greater than or equal to threshold

In this approach, we are going to apply sliding window technique, using two pointers left and right, take the moving sum of k elements, when the window size is reached, then compute the average as moving sum of k elements / k, if this is greater than or equal to threshold, add it to the result, and find how many such sub arrays are there by moving left and right pointers to next window.

Implementation steps:

First, we will create four variables left, right that we will use to adjust the window, result to hold the result, and movingSum to track the sum of current window's k elements.
Next, run a while loop until right pointer reaches end of array, and check:
- If the difference between right and left pointers are greater than K-1: This means that we are going out of window size k (since array is 0-indexed we are taking k-1 here), so check if the average movingSum/k is greater than or equal to threshold, if it is then we have found a subarray, so increment result. Then, subtract arr[left] from movingSum since we are going to move to next window, and increment left pointer by 1.
- Next, add current right pointer value to movingSum and increment right pointer.
Finally, return the result.

public class NumberOfSubArraysOfSizeKAndAvgGreaterThanOrEqualToThreshold { static int numOfSubarrays(int[] arr, int k, int threshold) { int result = 0; int left = 0; int right = 0; int movingSum = 0; while (right < arr.length) { if (right - left > k - 1) { if (movingSum / k >= threshold) { result++; } movingSum -= arr[left]; // subtract left pointer value from moving su, for next window left++; } movingSum += arr[right++]; } if (movingSum / k >= threshold) { result++; } return result; } public static void main(String[] args) { System.out.println(numOfSubarrays(new int[]{2, 2, 2, 2, 5, 5, 5, 8}, 3, 4)); System.out.println(numOfSubarrays(new int[]{11, 13, 17, 23, 29, 31, 7, 5, 2, 3}, 3, 5)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of arr array.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: