Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)

Date : August 30, 2024
Categories :
Tags :

Blazingly Fast Solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

Hello, fellow coding enthusiasts! Today, I tackled LeetCode problem #1342, titled “Number of Sub-arrays 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 sub-arrays of size k that have an average greater than or equal to the specified threshold.

To put it simply, for each sub-array 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 sub-array.

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 sub-array of size k, we can use a sliding window technique. This allows us to efficiently calculate the sum of the current sub-array 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 floating-point operations, we can rearrange the condition to check if sum >= k * threshold.
Count Valid Sub-arrays: Maintain a counter to keep track of how many valid sub-arrays 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 Sub-arrays: 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 sub-arrays, and mastering it can significantly improve your problem-solving 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!