209. Minimum Size Subarray Sum

Find the length of the shortest contiguous subarray whose sum is at least target. Because every value is positive, a variable-size window grows on the right and shrinks on the left in a single linear pass.

● MediumSliding WindowTwo PointersTypeScript

PROBLEM What we're solving

Return the length of the shortest contiguous subarray of nums (all positive) whose sum is ≥ target, or 0 if none qualifies. For target=7, nums=[2,3,1,2,4,3] the answer is 2 — the subarray [4,3] sums to 7 and no shorter window reaches 7.

KEY IDEA Positive values make the window monotonic

Insight → with only positive numbers, adding an element can only increase the running sum and removing one can only decreaseit. So once a window's sum reaches target, you can greedily shrink from the left to find the shortest window ending at the current right — no element ever needs to be re-added. One forward pass with two pointers suffices.

RECIPE Grow right, shrink left, record

0 · Init. left=0, sum=0, best=Infinity.
1 · Grow. Move right across the array, adding nums[right] to sum — this extends the window because more length means more sum.
2 · Shrink while qualifying. While sum ≥ target, record right - left + 1 as a candidate minimum, then subtract nums[left] and advance left — squeezing out slack to find the tightest valid window.
3 · Answer. Return best, or 0 if it was never updated.

Classic confusion → record the length before shrinking, while the window still satisfies sum ≥ target. If you shrink first and then measure, you log a window that may have already fallen below the target and report a wrong (too-long or invalid) length.

COST Complexity & alternatives

Check every subarray

O(n²)

Fix each start, extend until the sum hits target.

Sliding window

O(n)

Each index enters and leaves the window once. O(1) space.

Why the window is O(n)

Although the inner while nests inside the for, left only ever moves forward and never past right. Across the whole run each element is added once and removed once → 2n pointer moves total, i.e. O(n).

Pattern transfer → the grow/shrink window powers Longest Substring Without Repeating Characters, Minimum Window Substring, and Fruit Into Baskets. But it relies on positivity: if nums can contain negatives or zeros, the sum is no longer monotonic and shrinking is unsafe — switch to a prefix-sum + binary search or a monotonic-deque approach instead.

RUN IT Grow right, shrink left while sum ≥ target

target =nums =

step 0 / 17

STARTTarget 7. Grow a window from the right; whenever its sum reaches the target, record the length and shrink from the left.

1function minSubArrayLen(target: number, nums: number[]): number {
2▶  let left = 0;
3▶  let sum = 0;
4▶  let best = Infinity;
5 
6  for (let right = 0; right < nums.length; right++) {
7    sum += nums[right];              // grow the window
8    while (sum >= target) {          // window qualifies
9      best = Math.min(best, right - left + 1);
10      sum -= nums[left];            // shrink from the left
11      left++;
12    }
13  }
14  return best === Infinity ? 0 : best;
15}

state

left=0

right=–

sum=0

best=∞

current window [left…right]just added (right pointer)dropped on shrink

slowfast

TYPESCRIPT The solution, annotated

minSubArrayLen.ts
function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0;
  let sum = 0;
  let best = Infinity;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];              // grow the window
    while (sum >= target) {          // window qualifies
      best = Math.min(best, right - left + 1);
      sum -= nums[left];            // shrink from the left
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

Reading it block by block

Lines 2–4 — set up. left marks the window's start, sum is the running window sum, and best starts at Infinity so any real window beats it.

Lines 6–7 — grow. Sweep right across the array, adding each nums[right] into sum. Positivity guarantees the sum only goes up as the window widens.

Lines 8–9 — record then shrink. While the window already meets the target, log its length right - left + 1 as a candidate minimum. Recording before removing keeps the measured window valid.

Lines 10–11 — squeeze. Subtract nums[left] and advance left. The loop keeps shrinking while still ≥ target, so it finds the tightest window ending at this right.

Line 14 — answer. If best was never lowered, no window ever reached the target → return 0; otherwise return the shortest length found.

Complexity → O(n) time — each element is added once and removed once, so the pointers make at most 2n moves despite the nested loop. O(1) extra space.

INTERVIEWFollow-ups they'll ask

"What if nums can contain negatives or zeros?" The window stops being monotonic, so shrinking is unsafe. Use prefix sums with binary search, or a deque-based approach — O(n log n).
"Return the subarray itself, not just its length?" Track the left index whenever you update best and slice [bestLeft, bestLeft + best) at the end.
"Sum strictly greater than target?" Change the loop guard to sum > target; the structure is identical.
"Find the maximum-length subarray with sum ≤ target instead?" Same window skeleton, but shrink while the constraint is violated and record on the valid side.

OPTIMAL Sliding Window

minSubArrayLen.ts
function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0;
  let sum = 0;
  let best = Infinity;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];              // grow the window
    while (sum >= target) {          // window qualifies
      best = Math.min(best, right - left + 1);
      sum -= nums[left];            // shrink from the left
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

Complexity → O(n) time — each element is added once and removed once, so the pointers make at most 2n moves despite the nested loop. O(1) extra space.

ALT 1 Brute force — try every start

O(n²) time · O(1) space

Fix each starting index and extend rightward until the running sum reaches the target, tracking the shortest such window.

approach-2.ts
function minSubArrayLen(target: number, nums: number[]): number {
  let best = Infinity;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      if (sum >= target) {
        best = Math.min(best, j - i + 1);
        break;            // shortest window for this start
      }
    }
  }
  return best === Infinity ? 0 : best;
}

Note → Correct and easy to reason about, but re-scans overlapping ranges → O(n²). The sliding window avoids the rescans by never moving left backward.

ALT 2 Prefix sums + binary search

O(n log n) time · O(n) space

Build a strictly increasing prefix-sum array, then for each end binary-search the earliest start whose window still meets the target. This is the approach to reach for if values are not guaranteed positive only for the increasing-prefix trick.

approach-3.ts
function minSubArrayLen(target: number, nums: number[]): number {
  const n = nums.length;
  const prefix = new Array<number>(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

  let best = Infinity;
  for (let end = 1; end <= n; end++) {
    const need = prefix[end] - target;           // want prefix[start] <= need
    let lo = 0, hi = end;                         // find largest start with prefix[start] <= need
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (prefix[mid] <= need) lo = mid + 1;
      else hi = mid;
    }
    if (lo - 1 >= 0 && prefix[lo - 1] <= need) {
      best = Math.min(best, end - (lo - 1));
    }
  }
  return best === Infinity ? 0 : best;
}

Note → Slower than the linear window for this all-positive problem, but the prefix array stays sorted only because the values are positive; the binary-search framing is the bridge to variants that the simple window cannot handle.

MNEMONIC The one-liner

"Grow right, shrink left while you can, record before you cut."

TRIGGERS When you see _ → reach for _

"shortest/longest contiguous subarray"	variable-size sliding window
all values positive + sum threshold	grow right, shrink left (monotonic)
record length right − left + 1	candidate min before shrinking
negatives/zeros present	prefix sum + binary search instead

SKELETON The reusable shape

skeleton.ts
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;

FLASHCARDS Tap to flip

What makes the simple two-pointer window valid here?

All values are positive, so the running sum is monotonic — adding grows it, removing shrinks it.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

Optimal time complexity?

QUESTION 02

Why is the greedy shrink correct for this problem?

QUESTION 03

When should you record the candidate window length?

QUESTION 04

What does the function return when no subarray sums to at least target?

QUESTION 05

For target=7, nums=[2,3,1,2,4,3], the answer is:

QUESTION 06

If nums could contain negative numbers, the sliding window would fail because:

QUESTION 07

Across the whole run, how far does the left pointer travel?

QUESTION 08

#209 · Minimum Size Subarray SumFind the shortest contiguous subarray whose sum is at least target by growing a window to the right and shrinking from the left while it stays valid — an O(n) sweep that works because all values are positive.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Positive values make the window monotonic

RECIPE Grow right, shrink left, record

COST Complexity & alternatives

Why the window is O(n)

RUN IT Grow right, shrink left while sum ≥ target

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Sliding Window

ALT 1 Brute force — try every start

ALT 2 Prefix sums + binary search

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _