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

MediumArraySliding Window
Leetcode Link

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 kth 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The solution uses a sliding window technique to solve this problem efficiently. Here's how it works:

  1. Initial Window Sum: We first calculate the sum of the first k elements. This sum represents the total of the first window of size k. To decide if this window meets the requirements, we check if the average (the sum divided by k) is greater than or equal to the threshold.

  2. 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.

  3. 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 by ans += int(s / k >= threshold).

  4. 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 of arr.

  5. Return the Result: Once the iteration is complete, the variable ans holds the total number of sub-arrays of size k with an average greater than or equal to threshold. The function then returns ans.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example 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:

  1. Initial Window Sum:

    • First, we calculate the sum of the first k=3 elements [2, 5, 5]. The sum is 2 + 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 count ans = 1.

  2. 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 to threshold: 16 / 3 = 5.33 (greater than 4).
    • Increment our count: ans = 2.

  3. 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].

  4. 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 count ans = 3.

  5. Return the Result:

    • We return the final count ans, which is 3. Hence, there are three sub-arrays of size k with an average value greater than or equal to the threshold.

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
Not Sure What to Study? Take the 2-min Quiz：

How many times is a tree node visited in a depth first search?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Sliding Window Maximum

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫