Number Of Sub Arrays Of Size K And Average Greater Than Or Equal To Threshold - Leetcode Solution

Problem Statement:

Given an array of integers nums and two integers k and threshold.

Return the number of sub-arrays of size k and average greater than or equal to threshold.

Example 1:

Input: nums = [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).

Example 2:

Input: nums = [1,1,1,1,1], k = 1, threshold = 0 Output: 5

Example 3:

Input: nums = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5 Output: 6 Explanation: Sub-arrays [11,13,17], [13,17,23], [17,23,29], [23,29,31], [5,2,3] and [2,3,5] have averages 13, 17, 23, 27, 3 and 3 respectively. All other sub-arrays of size 3 have averages less than 5 (the threshold).

Solution:

To solve this problem, we can use a sliding window technique. We can start with a window of size k and calculate its average. If the average is greater than or equal to the threshold, we increment the count of sub-arrays. Then we slide the window by one element to the right and remove the leftmost element from the window and add the rightmost element to the window. We repeat this process until we reach the end of the array.

Let's look at the pseudo code for the algorithm:

count = 0 sum = 0 for i in range(k): sum += nums[i]

if sum / k >= threshold: count += 1

for i in range(k, len(nums)): sum -= nums[i - k] sum += nums[i]

if sum / k >= threshold:
    count += 1

return count

In the above algorithm, we initialize the count of sub-arrays to 0 and sum of first k elements to a variable called sum. We then calculate the average of the first k elements and check if it is greater than or equal to threshold. If it is true, we increment the count of sub-arrays.

We then slide the window by one element to the right and recalculate the sum by removing the leftmost element from the window and adding the rightmost element to the window. We repeat this process until we reach the end of the array.

At the end, we return the count of sub-arrays that have an average greater than or equal to threshold.

The time complexity of the above algorithm is O(n) where n is the length of the array nums.

1