1343. Number of Sub Arrays of Size K and Avg Greater than or Equal to Threshold - Explanation

Problem Link

Description

You are given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k and average greater than or equal to threshold.

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

Example 2:

Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5

Output: 6

Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Constraints:

• 1 <= k <= arr.length <= 100,000
• 1 <= arr[i] <= 10,000
• 0 <= threshold <= 10,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

For each valid starting position of a subarray of size k, we compute the sum of all elements in that window and check if the average meets the threshold. This approach recalculates the sum from scratch for every window.

Algorithm

1. Iterate through all possible starting indices l from 0 to n - k.
2. For each window, compute the sum of elements from index l to l + k - 1.
3. If sum / k >= threshold, increment the result counter.
4. Return the total count.

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        res = 0
        l = 0

        for r in range(k - 1, len(arr)):
            sum_ = 0
            for i in range(l, r + 1):
                sum_ += arr[i]

            if sum_ / k >= threshold:
                res += 1
            l += 1

        return res

Time & Space Complexity

• Time complexity: $O(n * k)$
• Space complexity: $O(1)$

Where $n$ is the size of the array $arr$ and $k$ is the size of the sub-array.

---

2. Prefix Sum

Intuition

Instead of recalculating sums from scratch, we precompute prefix sums. The sum of any subarray from index l to r becomes a simple subtraction: prefix[r+1] - prefix[l]. This trades memory for faster subarray sum queries.

Algorithm

1. Build a prefix sum array where prefix[i] holds the sum of elements from index 0 to i-1.
2. For each window of size k, compute the sum as prefix[r+1] - prefix[l].
3. If the average meets the threshold, increment the count.
4. Return the total count.

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        prefix_sum = [0] * (len(arr) + 1)
        for i in range(len(arr)):
            prefix_sum[i + 1] += prefix_sum[i] + arr[i]

        res = l = 0
        for r in range(k - 1, len(arr)):
            sum_ = prefix_sum[r + 1] - prefix_sum[l]
            if sum_ / k >= threshold:
                res += 1
            l += 1

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the size of the array $arr$ and $k$ is the size of the sub-array.

---

3. Sliding Window - I

Intuition

We maintain a running sum of the current window. When the window slides, we add the new element entering from the right and remove the element leaving from the left. This gives constant-time updates per window instead of recalculating from scratch.

Algorithm

1. Initialize curSum with the sum of the first k-1 elements.
2. For each starting position L:
   • Add the element at position L + k - 1 to complete the window.
   • Check if the average meets the threshold.
   • Remove the element at position L before moving to the next window.
3. Return the count of valid subarrays.

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        res = 0
        curSum = sum(arr[:k - 1])

        for L in range(len(arr) - k + 1):
            curSum += arr[L + k - 1]
            if (curSum / k) >= threshold:
                res += 1
            curSum -= arr[L]
        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ extra space.

Where $n$ is the size of the array $arr$ and $k$ is the size of the sub-array.

---

4. Sliding Window - II

Intuition

A small optimization: instead of dividing the sum by k for each comparison, we multiply the threshold by k once upfront. This converts the average check into a simple sum comparison, avoiding repeated division.

Algorithm

1. Multiply threshold by k to get the target sum.
2. Expand the window by adding elements from the right.
3. Once the window reaches size k:
   • Check if the current sum meets or exceeds the target.
   • Shrink the window from the left by removing the oldest element.
4. Return the count of valid subarrays.

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        threshold *= k
        res = curSum = 0
        for R in range(len(arr)):
            curSum += arr[R]
            if R >= k - 1:
                res += curSum >= threshold
                curSum -= arr[R - k + 1]
        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ extra space.

Where $n$ is the size of the array $arr$ and $k$ is the size of the sub-array.