FAANG · LeetCode #209

Minimum Size Subarray Sum — three-stage drill

1The ProblemMedium

Minimum Size Subarray Sum

Shortest contiguous subarray whose sum is at least the target.

Examples

[2,3,1,2,4,3], t=7→ 2[1,2,3], t=7→ 0

constraintAll numbers are positive (1 ≤ nums[i]).

2The PatternTIME O(n) · SPACE O(k)

Sliding Window

A contiguous window that grows and shrinks to stay valid.

Problems using this pattern

3The SolutionRESULT → 2

Step through it

right → 0: add 2. sum = 2 < 7

Step 1 / 11

Python▎shrink while valid

1def minSubArrayLen(target, nums):
2    left = total = 0
3    best = len(nums) + 1
4    for right in range(len(nums)):
5        total += nums[right]
6        while total >= target:
7            best = min(best, right - left + 1)
8            total -= nums[left]
9            left += 1
10    return 0 if best > len(nums) else best

why it worksWorks only because every number is positive: each shrink lowers the sum, so the window can never pass left over right (sum hits 0 < target first). Zeros or negatives break this — see #862, which needs prefix sums + a monotonic deque.

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Minimum Size Subarray Sum — three-stage drill