209. Minimum Size Subarray Sum

Quick Identifier

• Topic: sliding-window
• Pattern: Variable Window with Sum Threshold
• Hint: Expand the right pointer while accumulating the sum. When the sum reaches or exceeds the target, shrink from the left to find the minimal length.
• Difficulty: Medium
• Companies: Amazon, Google, Microsoft, Uber, Facebook
• LeetCode: 209

Quick Sights

• Time Complexity: O(n) – each element is visited at most twice (once by the right pointer, once by the left pointer).
• Space Complexity: O(1) – only a few integer counters are required.
• Core Mechanism: Maintain a running sum of the current window. When the sum >= target, update the answer with the window length and move the left edge to try to shrink the window while still meeting the threshold.

Concept Explanation

Think of the array as a river and the target sum as a dam you need to overflow. You constantly pour water (right pointer) into the reservoir (window). Once the water level reaches the dam height (target), you start releasing water from the left side to see how small a reservoir can still overflow.

1. Expand – add nums[right] to currentSum.
2. Check – if currentSum >= target, we have a valid subarray.
3. Contract – while the sum is still ≥ target, move left forward, subtracting nums[left], and record the smallest window size observed.

Diagram

Study Pattern (SDE3+)

• 0‑3 min: Explain the sliding‑window intuition and why a variable‑size window is needed instead of a fixed‑size one.
• Implementation pass: Emphasise the while sum >= target inner loop that shrinks the window and updates the answer.
• 5 min extension: Discuss the case where the input is a stream and you cannot store the entire array – you would maintain the same counters and a circular buffer of the last k elements if needed.

Approaches

• Brute force – check every subarray, O(n²).
• Prefix sum + binary search – O(n log n) but more complex.
• Optimal – sliding window with O(n) time, O(1) space. (Always pick this)

Optimal Solution

Go

func minSubArrayLen(target int, nums []int) int {
    left, sum, best := 0, 0, len(nums)+1
    for right, v := range nums {
        sum += v
        for sum >= target {
            if curLen := right - left + 1; curLen < best {
                best = curLen
            }
            sum -= nums[left]
            left++
        }
    }
    if best == len(nums)+1 {
        return 0
    }
    return best
}

JavaScript

function minSubArrayLen(target, nums) {
    let left = 0, sum = 0, best = Infinity;
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            best = Math.min(best, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return best === Infinity ? 0 : best;
}

Walkthrough

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

• Expand until right = 4 → sum = 12 ≥ 7, window [0,4] length 5.
• Shrink left: remove 2 → sum 10, length 4; remove 3 → sum 7, length 3 (record).
• Continue expanding; the minimal length found is 2 ([4,3]).
• Return 2.

Edge Cases

• No subarray meets the target → return 0.
• Single element ≥ target → answer is 1.
• Very large target greater than total sum → answer 0.

Pitfalls

• Forgetting to update best after shrinking the window; you might miss a smaller valid window.
• Using > instead of >= in the inner while condition – you would miss exact matches.
• Not handling the case where best stays at its initial sentinel value.

Similar Problems

• [1004. Max Consecutive Ones III] – variable window with a budget of flips.
• [209. Minimum Size Subarray Sum] – this exact problem.
• [209. Minimum Size Subarray Sum] – (duplicate reference for emphasis).

Mind‑Map Tags

#sliding-window #variable-window #sum-threshold #two-pointer #medium