1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold
Problem Description
The problem provides an array of integers arr
, along with two other integers k
and threshold
. The task is to determine how many continuous sub-arrays (consecutive elements) of arr
with size k
have an average value greater than or equal to threshold
. A sub-array's average is calculated by adding all the elements in the sub-array and then dividing by k
. The result should be the count of all sub-arrays that meet the specified average criterion.
Intuition
The intuition behind the solution relies on the concept of a sliding window. The window slides through the array, maintaining a fixed size of k
, and we compute the sum of the elements within this window. To find the average, we divide the sum by k
. If the average is greater than or equal to the threshold
, we increment our answer count.
Instead of recalculating the sum of elements each time the window moves, we can optimize this by subtracting the element that is left behind and adding the new element that comes into the window. This approach is efficient because it updates the sum by removing the exiting element and adding the entering element, thus requiring only a constant number of operations for each shift of the sliding window.
This is achieved in the solution by initially computing the sum of the first k
elements. Then, as we move the window across the array by iterating starting from the k
th element, we adjust the sum by simply adding the new element at the front and subtracting the last element of the previous window. After updating the sum, we check if the current average meets the threshold and increment our count accordingly.
Learn more about Sliding Window patterns.
Solution Approach
The solution uses a sliding window technique to solve this problem efficiently. Here's how it works:
-
Initial Window Sum: We first calculate the sum of the first
k
elements. This sum represents the total of the first window of sizek
. To decide if this window meets the requirements, we check if the average (the sum divided byk
) is greater than or equal to thethreshold
. -
Sliding the Window: After processing the first window, we iteratively move the window one element to the right. For each move, we perform the following actions:
- Add New Element: Include the new element (rightmost element of the new window) in the sum. This is done by
s += arr[i]
. - Remove Exiting Element: Exclude the leftmost element of the previous window from the sum. Achieved with
s -= arr[i - k]
. - These two operations effectively update the sum to reflect the total of the current window.
- Add New Element: Include the new element (rightmost element of the new window) in the sum. This is done by
-
Check and Count: After adjusting the sum for the current window, we check if the average meets or exceeds the
threshold
. If so, we increment our count by one. This is done byans += int(s / k >= threshold)
. -
Iterating Over the Array: We continue sliding the window and adjusting our sum and count until we've covered the entire array. The loop starts from
k
and goes till the end ofarr
. -
Return the Result: Once the iteration is complete, the variable
ans
holds the total number of sub-arrays of sizek
with an average greater than or equal tothreshold
. The function then returnsans
.
The beauty of this solution lies in its simplicity and efficiency. Instead of recalculating the sum for each sub-array from scratch, it smartly updates the existing sum, thus maintaining a constant time operation for each step in the window slide, which makes the algorithm O(n) where n is the number of elements in arr
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example to illustrate the solution approach. Suppose we have the following inputs:
arr = [2, 5, 5, 6, 3, 2, 2, 1]
k = 3
threshold = 4
Now, let's walk through the solution step by step:
-
Initial Window Sum:
- First, we calculate the sum of the first
k=3
elements[2, 5, 5]
. The sum is2 + 5 + 5 = 12
. - To check if this window meets the requirements, we compute the average:
12 / 3 = 4
. - The average is equal to the
threshold
of 4, so this window qualifies. Our initial countans = 1
.
- First, we calculate the sum of the first
-
Sliding the Window:
- We slide the window to the right to include the next element (
6
) and exclude the first element (2
) of the prior window. - We update the sum:
12 (previous sum) + 6 (new element) - 2 (exiting element) = 16
. - We check if the new window
[5, 5, 6]
has an average greater than or equal tothreshold
:16 / 3 = 5.33
(greater than 4). - Increment our count:
ans = 2
.
- We slide the window to the right to include the next element (
-
Repeat the Process:
- Slide the window to the next position:
[5, 6, 3]
. - Update the sum:
16 (previous sum) + 3 (new element) - 5 (exiting element) = 14
. - Check the average:
14 / 3 ≈ 4.67
(greater than 4). Increment the count:ans = 3
. - Continue this process for the rest of the array:
[6, 3, 2]
,[3, 2, 2]
, and finally[2, 2, 1]
.
- Slide the window to the next position:
-
Final Count:
- After processing all windows we find that only the windows
[2, 5, 5]
,[5, 5, 6]
, and[5, 6, 3]
meet the threshold average. Therefore, the final countans = 3
.
- After processing all windows we find that only the windows
-
Return the Result:
- We return the final count
ans
, which is3
. Hence, there are three sub-arrays of sizek
with an average value greater than or equal to the threshold.
- We return the final count
Solution Implementation
1from typing import List
2
3class Solution:
4 def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
5 # Initialize the sum of the first 'k' elements
6 current_sum = sum(arr[:k])
7
8 # Calculate the initial average and check if it meets or exceeds the threshold.
9 # Convert the comparison result to an integer (True becomes 1, False becomes 0).
10 subarrays_count = int(current_sum / k >= threshold)
11
12 # Iterate over the array starting from the k-th element.
13 for i in range(k, len(arr)):
14 # Update the sum by adding the new element and subtracting the oldest element (sliding window).
15 current_sum += arr[i] - arr[i - k]
16
17 # Check if the updated average meets or exceeds the threshold and update the count.
18 subarrays_count += int(current_sum / k >= threshold)
19
20 # Return the number of subarrays where the average is greater or equal to the threshold.
21 return subarrays_count
22
23# Example usage:
24# sol = Solution()
25# print(sol.numOfSubarrays([2, 1, 3, 4, 1], 3, 2)) # Output: 3
26
1class Solution {
2 public int numOfSubarrays(int[] arr, int k, int threshold) {
3 // Initialize the sum of the first 'k' elements.
4 int sum = 0;
5 for (int i = 0; i < k; ++i) {
6 sum += arr[i];
7 }
8
9 // Calculate the initial average and determine if it meets or exceeds the threshold.
10 // Increment the count if it does.
11 int count = (sum / k >= threshold) ? 1 : 0;
12
13 // Slide the window of size 'k' across the array and update the sum and count accordingly.
14 for (int i = k; i < arr.length; ++i) {
15 // Update the sum by adding the new element and subtracting the oldest element.
16 sum += arr[i] - arr[i - k];
17
18 // If the updated average meets or exceeds the threshold, increase the count.
19 count += (sum / k >= threshold) ? 1 : 0;
20 }
21
22 // Return the total count of subarrays that meet the threshold condition.
23 return count;
24 }
25}
26
1#include <vector>
2#include <numeric> // Include necessary headers
3
4class Solution {
5public:
6 int numOfSubarrays(vector<int>& arr, int k, int threshold) {
7 // Calculate the sum of the first 'k' elements
8 int windowSum = accumulate(arr.begin(), arr.begin() + k, 0);
9
10 // Initialize the count of subarrays with sum above the threshold
11 int count = (windowSum >= k * threshold) ? 1 : 0;
12
13 // Loop over the elements of the array, starting from the 'k'th element
14 for (int i = k; i < arr.size(); ++i) {
15 // Slide the window by one element to the right: subtract the element leaving the window
16 // and add the new element
17 windowSum += arr[i] - arr[i - k];
18
19 // If the new window sum satisfies the threshold condition, increment the count
20 count += (windowSum >= k * threshold) ? 1 : 0;
21 }
22
23 // Return the final count of subarrays
24 return count;
25 }
26};
27
28// Note: To use the updated code, you'll need to have '#include <vector>' and '#include <numeric>'
29// at the top of your code to bring in the necessary functionality from the C++ standard library.
30
1function numOfSubarrays(arr: number[], k: number, threshold: number): number {
2 // Initialize the sum of the first 'k' elements
3 let sum = arr.slice(0, k).reduce((accumulator, current) => accumulator + current, 0);
4
5 // Check if the average of the first 'k' elements meets or exceeds the threshold
6 // If it does, we increment our answer count 'subarrayCount'
7 let subarrayCount = sum >= k * threshold ? 1 : 0;
8
9 // Iterate over the array starting from the 'k'th element
10 for (let i = k; i < arr.length; ++i) {
11 // Update the sum to include the next element and exclude the (i-k)'th element
12 sum += arr[i] - arr[i - k];
13
14 // Check if the updated sum's average meets or exceeds the threshold,
15 // if so, increment 'subarrayCount'
16 subarrayCount += sum >= k * threshold ? 1 : 0;
17 }
18
19 // Return the total count of subarrays that have met or exceeded the threshold average
20 return subarrayCount;
21}
22
Time and Space Complexity
The provided code has a time complexity of O(n)
where n
is the length of the array. This linear time complexity arises because the code iterates over the array once, performing a constant number of operations for each element in the array after initializing a sum of the first k
elements.
The key to achieving O(n)
time complexity lies in the sliding window technique used to calculate the sum of each subarray of length k
. Instead of recalculating the sum from scratch, the code maintains the sum of the current window by subtracting the element that is leaving the window and adding the new element that enters the window. This update happens in constant time O(1)
.
The space complexity of the code is O(1)
since the code only uses a fixed amount of additional space. Variables s
and ans
do not depend on the size of the input array and only a constant amount of extra space is used regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.