Number Of Sub Arrays Of Size K And Avg Greater Than Or Equal To Threshold

Welcome to another coding tutorial!

In this post, we will tackle the LeetCode problem titled "Number of Sub Arrays of Size K and Average Greater than or Equal to Threshold." This problem falls under the category of sliding window algorithms and can be particularly interesting for those looking to sharpen their problem-solving skills.

By the end of this guide, you will have a clear understanding of how to approach and solve this problem effectively.

To get a comprehensive grasp of the problem statement, let's start by looking at the question itself.

Question

Problem Name: Number of Sub Arrays of Size K and Avg Greater than or Equal to Threshold

Difficulty: Medium

Category: Sliding Window

Companies: Amazon

Problem Statement:

You are given an array of integers arr and two integers k and threshold.

Your task is to determine the number of sub-arrays of size k where the average of the sub-array is greater than or equal to the given threshold.

Here's an example to illustrate the problem:

Example 1:

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 of 4, 5, and 6, respectively.
– All other sub-arrays of size 3 have averages less than 4 (the threshold).

This is just one example, and we need to solve this problem for various input arrays and different values of k and threshold.

Now, let's dive into the problem overview to understand the approach better.

Problem Overview

This problem is an excellent candidate for the sliding window technique, a popular strategy for efficiently solving subarray-related problems.

In the sliding window approach, we maintain a window of elements within the array and move it through the array while keeping track of certain conditions or calculations.

In this case, we're interested in the average of sub-arrays of size k and whether it meets the threshold.

Example 1:

Let's walk through the example provided to gain a deeper understanding of how this problem can be approached:

Input:
arr = [2, 2, 2, 2, 5, 5, 5, 8] k = 3 threshold = 4

We have an array arr, and our goal is to find sub-arrays of size k = 3 with an average greater than or equal to threshold = 4.

Starting at the beginning, we can build our sub-arrays as follows:

[2, 2, 2] – Average: (2 + 2 + 2) / 3 = 2. This sub-array does not meet the threshold.
[2, 2, 5] – Average: (2 + 2 + 5) / 3 = 3. This sub-array does not meet the threshold.
[2, 5, 5] – Average: (2 + 5 + 5) / 3 = 4. This sub-array meets the threshold.
[5, 5, 5] – Average: (5 + 5 + 5) / 3 = 5. This sub-array also meets the threshold.
[5, 5, 8] – Average: (5 + 5 + 8) / 3 = 6. This sub-array meets the threshold.
Moving forward is not necessary since we can't form a sub-array of size k anymore.

Out of the sub-arrays we've examined, three of them meet the threshold, and that's our final result, which is 3.

Understanding Threshold Constraints

Before we proceed with the solution, it's crucial to understand the constraints:

1 <= arr.length <= 10^5: The length of the input array arr can range from 1 to 100,000 elements.
1 <= arr[i] <= 10^4: Each element of the array arr is between 1 and 10,000.
1 <= k <= arr.length: The size of the sub-array, k, ranges from 1 to the length of the array.
0 <= threshold <= 10^4: The threshold is a non-negative integer, ranging from 0 to 10,000. Now, let's explore the solution to this problem.

Number of Sub Arrays of Size K and Avg Greater than or Equal to Threshold LeetCode Problem Solution

To tackle this problem, we'll implement the sliding window technique.

This approach allows us to efficiently iterate through the array, calculating sub-array averages and checking if they meet the threshold.

Here's the Python solution:

View on GitHub ➹

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -&gt; int:
        result = 0
        current_sum = sum(arr[:k - 1])

        for left in range(len(arr) - k + 1):
            current_sum += arr[left + k - 1]
            if (current_sum / k) &gt;= threshold:
                result += 1
            current_sum -= arr[left]

        return result

Now, let's break down the code step by step.

1. Bruteforce Approach

In this Python solution, we define a class Solution and a method numOfSubarrays.

This method takes three parameters:
– arr: The input array of integers.
– k: The size of the sub-array we want to create.
– threshold: The threshold value for the average of sub-arrays.

Inside the numOfSubarrays method, we initialize two variables:
– result: This variable will store the number of sub-arrays that meet the threshold condition.
– current_sum: We use this variable to keep track of the sum of the first k - 1 elements in the array.

We start by calculating the sum of the first k - 1 elements.

This initial sum helps us avoid recalculating the entire sub-array for each step.

The sum(arr[:k - 1]) operation achieves this.

Now, we enter a loop that iterates through the array, and we slide our window.

The loop variable left represents the leftmost index of our current window.

The loop will run for len(arr) - k + 1 iterations, ensuring that we go through every valid position in the array.

Within the loop, we update our current_sum by adding the value at the rightmost index of our current window, which is arr[left + k - 1].

This operation simulates sliding our window to the right.

We then check whether the average of the current sub-array meets or exceeds the threshold value.

If it does, we increment the result variable, as we've found a sub-array

that satisfies the condition.

Finally, before moving to the next iteration, we adjust the current_sum by subtracting the value at the leftmost index of the previous window.

This step ensures that we efficiently maintain our sum as we slide the window.

2. Efficient Approach with Sliding Window

The provided Python code implements an efficient solution using the sliding window technique.

It efficiently calculates the number of sub-arrays meeting the threshold condition.

The sliding window approach allows us to avoid redundant calculations and achieve a time complexity of O(n) for this problem.

Time and Space Complexity

Time Complexity:

The time complexity of the solution is O(n), where n represents the length of the input array arr.

We iterate through the array once, and within each iteration, we perform constant-time operations.

Space Complexity:

The space complexity is constant, denoted as O(1).

We use a fixed amount of additional space to store variables, regardless of the input size.

This is a memory-efficient solution.

Reasoning Behind Our Approach

The key to solving this problem efficiently lies in recognizing the sliding window pattern.

By using a single pointer to iterate through the array while maintaining a window of elements, we avoid recalculating the entire sub-array's sum.

Instead, we update the sum incrementally as we slide the window, which significantly improves our solution's efficiency.

Conclusion

In this post, we tackled the LeetCode problem "Number of Sub Arrays of Size K and Average Greater than or Equal to Threshold." We applied the sliding window technique to efficiently solve this problem, achieving a time complexity of O(n).

By understanding the problem's constraints, implementing the solution, and reasoning through the approach, you are now equipped to handle similar problems.

If you found this guide helpful, please like, engage, and share your thoughts in the comments section.

We encourage questions, suggestions, and discussions.

Your feedback is invaluable!

To access the original problem on LeetCode and practice the solution, you can visit the following link: Number of Sub Arrays of Size K and Average Greater than or Equal to Threshold.

Happy coding!