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

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

Topics

Array Sliding Window

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sliding Window Technique - Efficiently processing fixed-size subarrays by adding/removing elements at window boundaries
Prefix Sum - Precomputing cumulative sums to enable O(1) range sum queries
Array Traversal - Iterating through arrays with multiple pointers to define window boundaries

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

Iterate through all possible starting indices l from 0 to n - k.
For each window, compute the sum of elements from index l to l + k - 1.
If sum / k >= threshold, increment the result counter.
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

public class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int res = 0, l = 0;

        for (int r = k - 1; r < arr.length; r++) {
            int sum = 0;
            for (int i = l; i <= r; i++) {
                sum += arr[i];
            }
            if (sum / k >= threshold) {
                res++;
            }
            l++;
        }
        return res;
    }
}

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int res = 0, l = 0;

        for (int r = k - 1; r < arr.size(); r++) {
            int sum = 0;
            for (int i = l; i <= r; i++) {
                sum += arr[i];
            }
            if (sum / k >= threshold) {
                res++;
            }
            l++;
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @param {number} k
     * @param {number} threshold
     * @return {number}
     */
    numOfSubarrays(arr, k, threshold) {
        let res = 0,
            l = 0;

        for (let r = k - 1; r < arr.length; r++) {
            let sum = 0;
            for (let i = l; i <= r; i++) {
                sum += arr[i];
            }
            if (sum / k >= threshold) {
                res++;
            }
            l++;
        }
        return res;
    }
}

public class Solution {
    public int NumOfSubarrays(int[] arr, int k, int threshold) {
        int res = 0;
        int l = 0;

        for (int r = k - 1; r < arr.Length; r++) {
            int sum = 0;
            for (int i = l; i <= r; i++) {
                sum += arr[i];
            }

            if (sum / k >= threshold) {
                res++;
            }
            l++;
        }

        return res;
    }
}

func numOfSubarrays(arr []int, k int, threshold int) int {
    res := 0
    l := 0

    for r := k - 1; r < len(arr); r++ {
        sum := 0
        for i := l; i <= r; i++ {
            sum += arr[i]
        }
        if sum/k >= threshold {
            res++
        }
        l++
    }
    return res
}

class Solution {
    fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int {
        var res = 0
        var l = 0

        for (r in k - 1 until arr.size) {
            var sum = 0
            for (i in l..r) {
                sum += arr[i]
            }
            if (sum / k >= threshold) {
                res++
            }
            l++
        }
        return res
    }
}

class Solution {
    func numOfSubarrays(_ arr: [Int], _ k: Int, _ threshold: Int) -> Int {
        var res = 0
        var l = 0

        for r in (k - 1)..<arr.count {
            var sum = 0
            for i in l...r {
                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

Build a prefix sum array where prefix[i] holds the sum of elements from index 0 to i-1.
For each window of size k, compute the sum as prefix[r+1] - prefix[l].
If the average meets the threshold, increment the count.
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

public class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int[] prefixSum = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            prefixSum[i + 1] += prefixSum[i] + arr[i];
        }

        int res = 0, l = 0;
        for (int r = k - 1; r < arr.length; r++) {
            int sum = prefixSum[r + 1] - prefixSum[l];
            if (sum / k >= threshold) {
                res++;
            }
            l++;
        }
        return res;
    }
}

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        vector<int> prefixSum(arr.size() + 1);
        for (int i = 0; i < arr.size(); i++) {
            prefixSum[i + 1] += prefixSum[i] + arr[i];
        }

        int res = 0, l = 0;
        for (int r = k - 1; r < arr.size(); r++) {
            int sum = prefixSum[r + 1] - prefixSum[l];
            if (sum / k >= threshold) {
                res++;
            }
            l++;
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @param {number} k
     * @param {number} threshold
     * @return {number}
     */
    numOfSubarrays(arr, k, threshold) {
        const prefixSum = new Int32Array(arr.length + 1);
        for (let i = 0; i < arr.length; i++) {
            prefixSum[i + 1] += prefixSum[i] + arr[i];
        }

        let res = 0,
            l = 0;
        for (let r = k - 1; r < arr.length; r++) {
            const sum = prefixSum[r + 1] - prefixSum[l];
            if (sum / k >= threshold) {
                res++;
            }
            l++;
        }
        return res;
    }
}

public class Solution {
    public int NumOfSubarrays(int[] arr, int k, int threshold) {
        int[] prefixSum = new int[arr.Length + 1];
        for (int i = 0; i < arr.Length; i++) {
            prefixSum[i + 1] = prefixSum[i] + arr[i];
        }

        int res = 0, l = 0;
        for (int r = k - 1; r < arr.Length; r++) {
            int sum = prefixSum[r + 1] - prefixSum[l];
            if (sum / k >= threshold) {
                res++;
            }
            l++;
        }

        return res;
    }
}

func numOfSubarrays(arr []int, k int, threshold int) int {
    prefixSum := make([]int, len(arr)+1)
    for i := 0; i < len(arr); i++ {
        prefixSum[i+1] = prefixSum[i] + arr[i]
    }

    res, l := 0, 0
    for r := k - 1; r < len(arr); r++ {
        sum := prefixSum[r+1] - prefixSum[l]
        if sum/k >= threshold {
            res++
        }
        l++
    }
    return res
}

class Solution {
    fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int {
        val prefixSum = IntArray(arr.size + 1)
        for (i in arr.indices) {
            prefixSum[i + 1] = prefixSum[i] + arr[i]
        }

        var res = 0
        var l = 0
        for (r in k - 1 until arr.size) {
            val sum = prefixSum[r + 1] - prefixSum[l]
            if (sum / k >= threshold) {
                res++
            }
            l++
        }
        return res
    }
}

class Solution {
    func numOfSubarrays(_ arr: [Int], _ k: Int, _ threshold: Int) -> Int {
        var prefixSum = [Int](repeating: 0, count: arr.count + 1)
        for i in 0..<arr.count {
            prefixSum[i + 1] = prefixSum[i] + arr[i]
        }

        var res = 0
        var l = 0
        for r in (k - 1)..<arr.count {
            let sum = prefixSum[r + 1] - prefixSum[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

Initialize curSum with the sum of the first k-1 elements.
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.
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

public class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int res = 0;
        int curSum = 0;

        for (int i = 0; i < k - 1; i++) {
            curSum += arr[i];
        }

        for (int L = 0; L <= arr.length - k; L++) {
            curSum += arr[L + k - 1];
            if ((curSum / k) >= threshold) {
                res++;
            }
            curSum -= arr[L];
        }

        return res;
    }
}

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int res = 0, curSum = 0;

        for (int i = 0; i < k - 1; i++) {
            curSum += arr[i];
        }

        for (int L = 0; L <= arr.size() - k; L++) {
            curSum += arr[L + k - 1];
            if ((curSum / k) >= threshold) {
                res++;
            }
            curSum -= arr[L];
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @param {number} k
     * @param {number} threshold
     * @return {number}
     */
    numOfSubarrays(arr, k, threshold) {
        let res = 0;
        let curSum = 0;

        for (let i = 0; i < k - 1; i++) {
            curSum += arr[i];
        }

        for (let L = 0; L <= arr.length - k; L++) {
            curSum += arr[L + k - 1];
            if (curSum / k >= threshold) {
                res++;
            }
            curSum -= arr[L];
        }

        return res;
    }
}

public class Solution {
    public int NumOfSubarrays(int[] arr, int k, int threshold) {
        int res = 0;
        int curSum = 0;

        for (int i = 0; i < k - 1; i++) {
            curSum += arr[i];
        }

        for (int L = 0; L <= arr.Length - k; L++) {
            curSum += arr[L + k - 1];
            if (curSum / k >= threshold) {
                res++;
            }
            curSum -= arr[L];
        }

        return res;
    }
}

func numOfSubarrays(arr []int, k int, threshold int) int {
    res := 0
    curSum := 0

    for i := 0; i < k-1; i++ {
        curSum += arr[i]
    }

    for L := 0; L <= len(arr)-k; L++ {
        curSum += arr[L+k-1]
        if curSum/k >= threshold {
            res++
        }
        curSum -= arr[L]
    }
    return res
}

class Solution {
    fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int {
        var res = 0
        var curSum = 0

        for (i in 0 until k - 1) {
            curSum += arr[i]
        }

        for (L in 0..arr.size - k) {
            curSum += arr[L + k - 1]
            if (curSum / k >= threshold) {
                res++
            }
            curSum -= arr[L]
        }
        return res
    }
}

class Solution {
    func numOfSubarrays(_ arr: [Int], _ k: Int, _ threshold: Int) -> Int {
        var res = 0
        var curSum = 0

        for i in 0..<(k - 1) {
            curSum += arr[i]
        }

        for L in 0...(arr.count - k) {
            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

Multiply threshold by k to get the target sum.
Expand the window by adding elements from the right.
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.
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

public class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        threshold *= k;
        int res = 0, curSum = 0;

        for (int R = 0; R < arr.length; R++) {
            curSum += arr[R];
            if (R >= k - 1) {
                if (curSum >= threshold) {
                    res++;
                }
                curSum -= arr[R - k + 1];
            }
        }
        return res;
    }
}

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        threshold *= k;
        int res = 0, curSum = 0;

        for (int R = 0; R < arr.size(); R++) {
            curSum += arr[R];
            if (R >= k - 1) {
                if (curSum >= threshold) {
                    res++;
                }
                curSum -= arr[R - k + 1];
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @param {number} k
     * @param {number} threshold
     * @return {number}
     */
    numOfSubarrays(arr, k, threshold) {
        threshold *= k;
        let res = 0,
            curSum = 0;

        for (let R = 0; R < arr.length; R++) {
            curSum += arr[R];
            if (R >= k - 1) {
                if (curSum >= threshold) {
                    res++;
                }
                curSum -= arr[R - k + 1];
            }
        }
        return res;
    }
}

public class Solution {
    public int NumOfSubarrays(int[] arr, int k, int threshold) {
        threshold *= k;
        int res = 0, curSum = 0;

        for (int r = 0; r < arr.Length; r++) {
            curSum += arr[r];
            if (r >= k - 1) {
                if (curSum >= threshold) {
                    res++;
                }
                curSum -= arr[r - k + 1];
            }
        }

        return res;
    }
}

func numOfSubarrays(arr []int, k int, threshold int) int {
    threshold *= k
    res, curSum := 0, 0

    for r := 0; r < len(arr); r++ {
        curSum += arr[r]
        if r >= k-1 {
            if curSum >= threshold {
                res++
            }
            curSum -= arr[r-k+1]
        }
    }
    return res
}

class Solution {
    fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int {
        val target = threshold * k
        var res = 0
        var curSum = 0

        for (r in arr.indices) {
            curSum += arr[r]
            if (r >= k - 1) {
                if (curSum >= target) {
                    res++
                }
                curSum -= arr[r - k + 1]
            }
        }
        return res
    }
}

class Solution {
    func numOfSubarrays(_ arr: [Int], _ k: Int, _ threshold: Int) -> Int {
        let target = threshold * k
        var res = 0
        var curSum = 0

        for r in 0..<arr.count {
            curSum += arr[r]
            if r >= k - 1 {
                if curSum >= target {
                    res += 1
                }
                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.

Common Pitfalls

Integer Division Truncation

When computing sum / k in languages like Java, C++, or Go, integer division truncates toward zero. If the sum is 15 and k is 4, 15 / 4 equals 3, not 3.75. This can cause false negatives when the true average meets the threshold but the truncated result does not. Multiplying the threshold by k and comparing sums directly avoids this issue.

Recalculating the Window Sum

A common inefficiency is recalculating the sum for each window from scratch, leading to O(n*k) time complexity. The sliding window technique maintains a running sum, adding the new element and removing the old element in O(1) time per window.

Off-By-One Errors in Window Boundaries

When sliding the window, it is easy to make mistakes with index calculations. Ensure the window always contains exactly k elements. Common errors include starting the right pointer at the wrong index or incorrectly computing when to start shrinking the window from the left.