Minimum Size Subarray Sum
How to find the shortest contiguous stretch that sums to at least a target, expanding and shrinking a window instead of checking every stretch.
The job
You have a list of positive numbers and a target sum. Find the length of the SHORTEST contiguous stretch whose numbers add up to at least the target.
The obvious way
Try every possible start and end position, sum each stretch, and keep the shortest one that qualifies.For 6 numbers that is on the order of 21 stretches.
The idea
Grow a window from the right, one number at a time, adding to a running total. The moment the total reaches the target, the window is valid — so try shrinking it from the left, recording its length each time, until it stops being valid. Then keep growing from the right again.
Think of it like this. Filling a cart with groceries until the total crosses a budget threshold, then, once it has, seeing how many items you can remove from the BOTTOM of the cart before you dip back under. You never need to try every possible combination — just grow, then trim, then grow again.
Shortest window summing to at least 7
6 positive numbers. Find the SHORTEST contiguous window whose sum is at least 7.
def min_subarray_len(target, nums):
left = 0
total = 0
best = len(nums) + 1
for right in range(len(nums)):
total += nums[right]
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return best if best <= len(nums) else 0This run
Shortest window is 2 numbers long, positions 4 to 5 — found by expanding and shrinking one window instead of checking every stretch.
The names you just watched
left and right, both moving forward
Unlike Two Pointers or Container With Most Water, these two never converge toward each other — `right` only grows the window and `left` only shrinks it, both strictly left to right.
Shrink WHILE valid, not just once
After adding a number makes the window valid, the inner loop keeps trimming from the left as long as it stays valid — there can be several shrink beats for every one expand beat.
Why this is still O(n)
`left` never moves backward, so across the whole run it advances at most n times total, no matter how many outer steps trigger a shrink. Two pointers that only ever move forward add up to a single pass, not a pass per outer step.
How to spot a sliding-window problem
The tell: You need the shortest or longest contiguous stretch satisfying a condition that gets MONOTONICALLY easier to break as the window grows and easier to satisfy as it shrinks (or vice versa) — so a two-ended, both-forward window works.
Reach for it when
- The phrase "contiguous subarray" or "substring" appears, with a min/max length asked for.
- A brute-force answer checks every (start, end) pair.
- Adding an element to the window can only help satisfy the condition; removing one can only hurt it (or the reverse).
- All values are non-negative — a negative value would break the "growing only helps" guarantee.
Not this when
- Values can be negative, which breaks the monotone growth assumption this technique depends on.
- The window is not contiguous — order doesn't have to be adjacent.
- The validity condition depends on the FULL history, not just what is currently inside the window.
Practice
6 problemsThe lesson, exactly. Expand right to grow the sum, shrink left as long as the window is already valid.
Same expand-right, shrink-left shape, but the validity check is "no repeated character in the window" instead of a sum threshold — and it maximizes length instead of minimizing it.
The validity check becomes "the window contains every required character" — tracked with a frequency map instead of a running sum.
Validity is "window length minus the count of its most frequent character is at most k" — same shrink-while-invalid loop, a different formula.
Validity is "at most 2 distinct values in the window" — the same shape as Longest Substring Without Repeating Characters, phrased as fruit types.
Validity is "at most k zeros in the window" — a running count instead of a running sum, otherwise identical to this lesson.