Minimum Size Subarray Sum Solution

Problem

Given an array of positive integers and a target value, find the length of the shortest contiguous subarray whose elements sum to at least the target. Return 0 if no such subarray exists.

Input: target = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2
Explanation: The subarray [4, 3] has sum 7 and is the shortest with sum ≥ target.

Counter-example: target = 100, nums = [1, 2, 3] → return 0 because no subarray can reach 100.

Intuition

The problem asks for the shortest window with a large enough sum. Because all values are positive, extending the window right always increases the sum and shrinking it left always decreases the sum — this monotonic property is exactly what lets a two-pointer approach work. The key insight: as soon as a window's sum hits the target, greedily shrink from the left as far as possible before recording the minimum length.

Approach 1 — Brute Force

For each starting position, expand right until the sum reaches the target, then record the window length.

Initialize min_length to infinity as a sentinel for "not found".
For each starting index left, accumulate a running sum moving right.
The moment the running sum reaches the target, record the window length and break — no need to keep expanding from this left.
After all pairs, return min_length if it was ever updated, otherwise return 0.

1def minSubArrayLen(target: int, nums: list[int]) -> int:
2    min_length = float('inf')
3    n = len(nums)
4
5    for left in range(n):
6        current_sum = 0
7        for right in range(left, n):
8            current_sum += nums[right]
9            if current_sum >= target:
10                min_length = min(min_length, right - left + 1)
11                break  # extending right can only make it longer, not shorter
12
13    return 0 if min_length == float('inf') else min_length

Time: O(n²) — each pair (left, right) is considered at most once, but that's still quadratic.
Space: O(1) — only a handful of integer variables, no extra storage.

Approach 2 — Sliding Window

Maintain a window with two pointers. Right always advances; left advances whenever the window sum already meets the target, because shrinking cannot hurt (all values are positive, so a smaller valid window is always better).

Initialize left = 0, window_sum = 0, min_length = infinity.
Advance right through the array, adding each element to window_sum.
While window_sum >= target: record the current window length, then subtract nums[left] and advance left — the while loop (not just an if) is essential because after one shrink the window may still be valid.
After the loop, return min_length if updated, otherwise 0.

1def minSubArrayLen(target: int, nums: list[int]) -> int:
2    min_length = float('inf')
3    window_sum = 0
4    left = 0
5
6    for right in range(len(nums)):
7        window_sum += nums[right]
8
9        while window_sum >= target:
10            min_length = min(min_length, right - left + 1)  # record before shrinking
11            window_sum -= nums[left]
12            left += 1
13
14    return 0 if min_length == float('inf') else min_length

Time: O(n) — each element is added once when right passes over it, and removed at most once when left passes over it.
Space: O(1) — only a constant number of variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Only for very small arrays or when code simplicity is the only priority
Sliding Window	O(n)	O(1)	Always — handles any input size efficiently and is no harder to read

Common Mistakes

Using > instead of >= — the problem says "greater than or equal to" the target, so a window summing to exactly the target is valid; > would miss it.
Using if instead of while to shrink — after removing nums[left], the remaining window might still be ≥ target and could shrink further; stopping after one shrink leaves a longer-than-necessary window recorded.
Recording the window length after incrementing left — right - left + 1 should be computed before moving left, or you'll count one fewer element than is in the current valid window.
Initializing min_length to n instead of n+1 or infinity — if the answer is exactly n (the whole array), you'd never update from the initial value and mistakenly think no window was found.
Assuming this pattern works with negative numbers — the entire approach relies on "adding an element always increases the sum." With negatives present, a larger window could actually have a smaller sum, and the while loop would never terminate correctly. This solution is only valid because the problem guarantees positive integers.

Minimum Size Subarray Sum — Solution