Blazingly fast solution to LeetCode #1342  Number of Subarrays of Size K and Average Greater than or Equal to Threshold (Crosspost from r/SoftwareEngineering)
Blazingly Fast Solution to LeetCode #1342  Number of Subarrays of Size K and Average Greater than or Equal to Threshold
Hello, fellow coding enthusiasts! Today, I tackled LeetCode problem #1342, titled “Number of Subarrays of Size K and Average Greater than or Equal to Threshold.” This problem is an interesting challenge that tests your understanding of arrays and averages. I thought I’d share my approach and solution with you all, so let’s dive in!
Problem Overview
The problem statement is straightforward: you are given an array of integers and two additional integers, k
and threshold
. Your task is to find the number of contiguous subarrays of size k
that have an average greater than or equal to the specified threshold
.
To put it simply, for each subarray of size k
, you need to calculate its average and check if it meets or exceeds the threshold. If it does, we count it as a valid subarray.
Breaking Down the Solution
Before jumping into the code, let’s outline the key steps we need to take:

Calculate the Sliding Window: Instead of recalculating the sum for every possible subarray of size
k
, we can use a sliding window technique. This allows us to efficiently calculate the sum of the current subarray and update it as we move through the main array. 
Check the Average: For each window, we will check if the average is greater than or equal to the threshold. To avoid floatingpoint operations, we can rearrange the condition to check if
sum >= k * threshold
. 
Count Valid Subarrays: Maintain a counter to keep track of how many valid subarrays we find that meet the required condition.
The Code
Here’s how the solution looks in Python:
def numOfSubarrays(arr, k, threshold):
count = 0
current_sum = sum(arr[:k])
if current_sum >= k * threshold:
count += 1
for i in range(k, len(arr)):
current_sum += arr[i]  arr[i  k]
if current_sum >= k * threshold:
count += 1
return count
Explanation of the Code

Initialization: We first calculate the sum of the first
k
elements in the array and check if it meets the threshold condition. 
Sliding Window Technique: We then iterate through the array starting from the
k
th element. For each new element added to the window, we subtract the element that is sliding out of the window. This efficient adjustment keeps our time complexity down to O(n). 
Count Valid Subarrays: Each time the current sum meets the threshold condition, we increment our count.
Complexity Analysis
 Time Complexity: O(n), where
n
is the length of the input array. We traverse the array just once.  Space Complexity: O(1), since we are only using a fixed amount of extra space for the counters and sums.
Conclusion
I had a lot of fun solving this problem, and I hope my solution helps you as well! The sliding window technique is a powerful tool for problems involving contiguous subarrays, and mastering it can significantly improve your problemsolving skills.
Feel free to check out my full solution and detailed explanation on my website here.
I would love to hear your thoughts on my solution! Did you tackle this problem differently? What strategies did you find helpful? Share your insights in the comments below!
Happy coding!