Minimum Size Subarray Sum (LeetCode 209)

The problem

You get an array of positive integers nums and a positive integer target. Return the length of the shortest contiguous subarray whose sum is at least target. If none exists, return 0.

Input:  target = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2

The subarray [4, 3] sums to 7, and no single element reaches 7.

How to think about it

Start with brute force. For each start index, extend to the right adding numbers until the sum reaches target, and record the length. That’s O(n²).

Use the fact that all numbers are positive. Adding an element always increases the sum, and removing one always decreases it. That makes the “sum ≥ target” condition well behaved: if a window is valid, extending it keeps it valid; if it’s invalid, shrinking it keeps it invalid.

The key insight: grow to become valid, then shrink to become short. Move the right edge forward, adding to a running sum. The moment the sum reaches target, you have a valid window, but maybe not the shortest one ending here. So shrink from the left while the sum is still at least target, recording the length each time. When it drops below, go back to growing. Every element is added once and removed once.

Which pattern is this? A variable-size sliding window, the “minimum length” flavour. The tell is “shortest subarray with sum ≥ target, all positive numbers”. If negatives are allowed, this breaks and you need prefix sums with a monotonic deque instead.

Approach

1. Keep start = 0, running sum s = 0, best = infinity.
2. For each i, add nums[i] to s.
3. While s >= target: record i - start + 1 in best, subtract nums[start], and move start right.
4. At the end, return 0 if best is still infinity, otherwise best.

Solution

def min_subarray_len(target, nums):
    start = 0; s = 0; best = float('inf')
    for i, x in enumerate(nums):
        s += x                                    # grow on the right
        while s >= target:                        # valid: try to shrink
            best = min(best, i - start + 1); s -= nums[start]; start += 1
    return 0 if best == float('inf') else best
# min_subarray_len(7, [2,3,1,2,4,3]) -> 2

Dry run

On target = 7, nums = [2, 3, 1, 2, 4, 3]:

The answer is 2.

Complexity

• Time: O(n). Each element is added once and subtracted at most once, so the inner while runs at most n times in total.
• Space: O(1). A sum, a best length, and two indices.

Edge cases and pitfalls

• No valid subarray (the whole array sums below target): best stays infinity, so return 0.
• A single element already ≥ target: the answer is 1.
• Using if instead of while to shrink misses shorter windows when several elements can be dropped at once, as at i = 4 above.
• Negative numbers break the logic, because shrinking can increase the sum. The problem promises positives; say so in the interview.
• Recording the length after shrinking instead of before gives a window that’s already invalid.

Related problems

• Minimum Window Substring (LeetCode 76): the same grow-then-shrink template with character counts.
• Max Consecutive Ones III (LeetCode 1004): the “longest valid window” counterpart.
• Subarray Sum Equals K (LeetCode 560): when numbers can be negative, use prefix sums and a hash map instead.