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

Problem Description

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.

Key Insights

• A sub-array of size k has an average that can be calculated by summing its elements and dividing by k.
• To check if the average of a sub-array is greater than or equal to threshold, we can compare the sum of the sub-array to k * threshold.
• A sliding window approach can be utilized to efficiently compute the sums of sub-arrays of size k without recalculating the sum from scratch for each sub-array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a sliding window technique. The algorithm involves maintaining a running sum of the current window of size k. We start by calculating the sum of the first k elements. As we slide the window to the right, we subtract the element that is leaving the window and add the element that is entering the window. This allows us to efficiently compute the sum of each sub-array of size k. For each sum, we check if it is greater than or equal to k * threshold to count the valid sub-arrays.

Code Solutions