LeetCode Problem 1343

Difficulty: 🟡 Medium
Topics: Array, Sliding Window

Solution

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

Problem Understanding

This problem asks us to count how many contiguous subarrays of length k have an average value greater than or equal to a given threshold.

The input consists of:

• An integer array arr
• An integer k, representing the fixed size of each subarray
• An integer threshold

A subarray is a continuous portion of the array. For every possible subarray of exactly length k, we compute its average and check whether that average is at least threshold.

The final answer is simply the number of qualifying subarrays.

For example, suppose:

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

The possible subarrays of size 3 are:

[2,2,2]
[2,2,2]
[2,2,5]
[2,5,5]
[5,5,5]
[5,5,8]

Among these, the last three have averages greater than or equal to 4, so the answer is 3.

The constraints are important:

• arr.length can be as large as 100000
• Each value can be up to 10000

These limits immediately suggest that an inefficient solution could time out. In particular, recomputing the sum of every subarray from scratch would be too slow for large inputs.

There are also several edge cases worth considering:

• When k = 1, every individual element forms a valid subarray.
• When k = arr.length, there is only one possible subarray.
• When no subarray satisfies the condition, the answer should be 0.
• When every subarray satisfies the condition, the answer should equal the total number of windows.
• Averages are not guaranteed to be integers, so using integer division incorrectly could introduce bugs.

An important observation is that we do not actually need to compute averages directly. Since:

average = sum / k

The condition:

average >= threshold

is equivalent to:

sum >= threshold * k

This transformation avoids floating point arithmetic entirely.

Approaches

Brute Force Approach

The most straightforward solution is to examine every possible subarray of size k.

For each starting index:

1. Compute the sum of the next k elements.
2. Divide by k to compute the average.
3. Compare the average against threshold.
4. Increment the answer if the condition is satisfied.

This approach is correct because it explicitly checks every valid subarray.

However, it is inefficient. If there are n elements, then there are approximately n - k + 1 subarrays. Computing the sum of each subarray requires O(k) work.

That leads to a total complexity of:

O((n - k + 1) * k)

In the worst case, this becomes O(n * k), which can approach 10^10 operations for large inputs.

Optimal Sliding Window Approach

The key observation is that consecutive subarrays overlap heavily.

Consider these windows:

[2,2,2]
[2,2,5]

The second window differs from the first by:

• Removing the leftmost element
• Adding one new rightmost element

Instead of recomputing the entire sum each time, we can maintain a running window sum.

This is exactly what the sliding window technique is designed for.

The algorithm works by:

1. Computing the sum of the first window.
2. Checking whether it satisfies the condition.
3. Sliding the window one position at a time:

• Subtract the outgoing element
• Add the incoming element

4. Repeating until all windows are processed.

This reduces the complexity to linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × k)	O(1)	Recomputes every window sum from scratch
Optimal Sliding Window	O(n)	O(1)	Reuses previous window sum efficiently

Algorithm Walkthrough

Optimal Sliding Window Algorithm

1. Compute the required minimum window sum.

Instead of checking:

average >= threshold

we check:

sum >= threshold * k

This avoids floating point arithmetic and makes comparisons simpler and faster. 2. Compute the sum of the first k elements.

This initializes the first sliding window. 3. Check whether the first window satisfies the condition.

If the current window sum is at least the required sum, increment the answer. 4. Slide the window across the array.

For every new position:

• Remove the element leaving the window
• Add the new element entering the window

This updates the window sum in constant time. 5. After updating the window sum, check the condition again.

If the updated window satisfies the threshold requirement, increment the answer. 6. Continue until the window reaches the end of the array. 7. Return the total count.

Why It Works

The sliding window always represents exactly one contiguous subarray of size k.

When the window moves one step to the right:

• One element leaves
• One new element enters

Updating the running sum preserves the exact sum of the current window at all times. Since every possible window of size k is processed exactly once, and every qualifying window increments the count, the final answer is correct.

Python Solution

from typing import List

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        required_sum = k * threshold
        
        window_sum = sum(arr[:k])
        count = 0
        
        if window_sum >= required_sum:
            count += 1
        
        for right in range(k, len(arr)):
            window_sum += arr[right]
            window_sum -= arr[right - k]
            
            if window_sum >= required_sum:
                count += 1
        
        return count

The implementation begins by converting the average comparison into a sum comparison using:

required_sum = k * threshold

This avoids floating point operations entirely.

Next, the code computes the sum of the first window using:

window_sum = sum(arr[:k])

This establishes the initial sliding window.

The algorithm then checks whether this first window satisfies the condition.

The main loop begins at index k, which represents the first new element entering the window. For each iteration:

window_sum += arr[right]
window_sum -= arr[right - k]

The first statement adds the new incoming element. The second removes the outgoing element from the previous window.

This keeps the window size fixed at exactly k.

After updating the sum, the algorithm checks whether the current window qualifies and increments the answer accordingly.

Finally, the total count is returned.

Go Solution

func numOfSubarrays(arr []int, k int, threshold int) int {
    requiredSum := k * threshold

    windowSum := 0

    for i := 0; i < k; i++ {
        windowSum += arr[i]
    }

    count := 0

    if windowSum >= requiredSum {
        count++
    }

    for right := k; right < len(arr); right++ {
        windowSum += arr[right]
        windowSum -= arr[right-k]

        if windowSum >= requiredSum {
            count++
        }
    }

    return count
}

The Go implementation follows the exact same sliding window logic as the Python version.

One small difference is that Go does not provide a built in sum() function for slices, so the initial window sum is computed manually using a loop.

Integer overflow is not a concern here because:

maximum possible window sum = 100000 * 10000 = 10^9

which safely fits inside a 32 bit signed integer. Go's int type is sufficient.

The implementation uses constant extra memory and processes the array in a single pass.

Worked Examples

Example 1

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

Required sum:

threshold * k = 4 * 3 = 12

Initial window:

[2,2,2]
sum = 6

This does not qualify.

Window	Window Sum	Qualifies?	Count
[2,2,2]	6	No	0
[2,2,2]	6	No	0
[2,2,5]	9	No	0
[2,5,5]	12	Yes	1
[5,5,5]	15	Yes	2
[5,5,8]	18	Yes	3

Final answer:

3

Example 2

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

Required sum:

5 * 3 = 15

Initial window:

[11,13,17]
sum = 41

This qualifies immediately.

Window	Window Sum	Qualifies?	Count
[11,13,17]	41	Yes	1
[13,17,23]	53	Yes	2
[17,23,29]	69	Yes	3
[23,29,31]	83	Yes	4
[29,31,7]	67	Yes	5
[31,7,5]	43	Yes	6
[7,5,2]	14	No	6
[5,2,3]	10	No	6

Final answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element enters and leaves the window at most once
Space	O(1)	Only a few integer variables are used

The algorithm performs a single linear scan across the array. Every iteration updates the running sum in constant time.

No additional data structures proportional to the input size are allocated, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        required_sum = k * threshold
        
        window_sum = sum(arr[:k])
        count = 0
        
        if window_sum >= required_sum:
            count += 1
        
        for right in range(k, len(arr)):
            window_sum += arr[right]
            window_sum -= arr[right - k]
            
            if window_sum >= required_sum:
                count += 1
        
        return count

solution = Solution()

assert solution.numOfSubarrays(
    [2,2,2,2,5,5,5,8], 3, 4
) == 3  # Provided example 1

assert solution.numOfSubarrays(
    [11,13,17,23,29,31,7,5,2,3], 3, 5
) == 6  # Provided example 2

assert solution.numOfSubarrays(
    [1], 1, 1
) == 1  # Single element qualifies

assert solution.numOfSubarrays(
    [1], 1, 2
) == 0  # Single element does not qualify

assert solution.numOfSubarrays(
    [5,5,5,5], 2, 5
) == 3  # Every window qualifies

assert solution.numOfSubarrays(
    [1,1,1,1], 2, 5
) == 0  # No window qualifies

assert solution.numOfSubarrays(
    [4,4,4,4], 4, 4
) == 1  # Entire array as one window

assert solution.numOfSubarrays(
    [7,7,7], 1, 7
) == 3  # k = 1 case

assert solution.numOfSubarrays(
    [10,20,30,40,50], 3, 30
) == 2  # Mixed qualifying windows

assert solution.numOfSubarrays(
    [10000] * 100000, 100000, 10000
) == 1  # Maximum size stress test

Test Case Summary

Test	Why
[2,2,2,2,5,5,5,8], k=3	Validates provided example
[11,13,17,23,29,31,7,5,2,3], k=3	Validates floating point average interpretation
[1], k=1, threshold=1	Smallest valid input
[1], k=1, threshold=2	Single window fails condition
[5,5,5,5], k=2	Every window qualifies
[1,1,1,1], k=2	No window qualifies
[4,4,4,4], k=4	Window equals full array
[7,7,7], k=1	Tests smallest window size
[10,20,30,40,50], k=3	Mixed qualifying and non qualifying windows
[10000] * 100000	Stress test for maximum constraints

Edge Cases

One important edge case occurs when k = 1. In this situation, every individual element forms its own subarray. A buggy implementation might incorrectly assume windows always contain multiple elements. The sliding window solution handles this naturally because the window size remains exactly one throughout execution.

Another important case occurs when k = arr.length. Here, only one subarray exists, the entire array itself. Some implementations accidentally attempt to slide beyond the valid range or mishandle initialization. This implementation computes the first window correctly and simply skips the sliding loop because there are no additional windows.

A subtle edge case involves averages that are not integers. For example:

sum = 10
k = 3
average = 3.333...

Using integer division could produce incorrect results. This implementation avoids division entirely by transforming the condition into:

sum >= threshold * k

This guarantees mathematically correct comparisons without floating point precision issues.

Another edge case is when no windows qualify. In that scenario, the count variable should remain zero throughout execution. Since the implementation only increments the count when the condition is satisfied, it naturally handles this case correctly.

Finally, very large inputs could expose performance problems in inefficient solutions. Since the algorithm processes each element only once and uses constant extra memory, it remains efficient even at the maximum constraint size of 100000 elements.