Sliding Window · LC #209

Minimum Size Subarray Sum

Variable-size sliding window: expand right to accumulate sum ≥ target, then greedily shrink from left to minimise window length. All-positive constraint makes shrinking safe.

mediumLC #209AMZ★★GOO★META★MSFT★AAPL★

Mark as done

Confidence

Ask GPT Practice on LeetCodePractice

Statement

Problem & Approach

Problem statement, sample I/O, and key reasoning.

Given a positive integer `target` and array of positive integers `nums`, return the minimum length of a contiguous subarray whose sum ≥ `target`. Return 0 if none exists.

Sample I/O

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

Input:  target=11, nums=[1,1,1,1,1,1,1,1]
Output: 0

Intuition

How to Think About It

Intuition

All elements are positive, so adding more elements always increases the sum and removing elements always decreases it. This monotone property lets us use a sliding window: expand right until sum ≥ target, then shrink left as long as sum remains ≥ target (each shrink might yield a shorter valid window).

Core Concept

Two pointers l=0, sum=0, min_len=infinity. For each r: sum += nums[r]. While sum >= target: min_len = min(min_len, r-l+1); sum -= nums[l]; l++. Return 0 if min_len unchanged, else min_len. Time O(n) (each element added/removed at most once), Space O(1).

When to use

Minimum-length subarray with sum ≥ target when all elements are positive. Any "shrink as far as valid" variable-window problem with a monotone sum property.

When NOT to use

When elements can be negative (the monotone property breaks - use prefix sums + binary search or deque). When you need maximum length (invert the shrink condition).

Key Insights

What to Know Cold

All-positive constraint is essential: without it, removing a positive element could increase the sum, breaking the while-loop termination logic.
The inner while loop looks nested O(n²) but each pointer moves right at most n times total - amortised O(n).
Shrink as far as possible (while sum >= target) to minimise window length - greedy correctness relies on positivity.
Binary search on prefix sums gives O(n log n) and works for non-negative arrays too.
Return 0 (not infinity) when no valid subarray exists - explicit check required.

1 example

Worked Examples

Variable window shrink - Python

Find min-length subarray with sum ≥ 7 in [2,3,1,2,4,3].

Expand right; while sum >= target shrink left and record length.

def minSubArrayLen(target: int, nums: list[int]) -> int:
    l = total = 0
    min_len = float('inf')
    for r, n in enumerate(nums):
        total += n
        while total >= target:
            min_len = min(min_len, r - l + 1)
            total -= nums[l]; l += 1
    return 0 if min_len == float('inf') else min_len
# target=7,[2,3,1,2,4,3] → 2

Output: 2

Demonstrates amortised O(n) two-pointer technique; the nested while looks quadratic but each element is visited at most twice.