209. Minimum Size Subarray Sum

209

MediumSliding WindowTwo pointers + running sumShrinking window on a sum threshold

Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is greater than or equal to target. If no such subarray exists, return 0.

Open official problem prompt ↗

In plain English

Find the fewest consecutive elements whose total reaches at least the target.

Picture it like this

Filling a bucket from a conveyor: keep adding items until the bucket is heavy enough, then remove from the front to see how light (short) a run still meets the weight.

Example

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Why: The subarray [4,3] sums to 7 (>= 7) and has length 2, the smallest possible.

Constraints

1 <= target <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^4

Pattern lesson

See the pattern, then code

Shrinking window on a sum threshold

↗

Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. Because all numbers are positive, adding elements only increases the sum, so once the window meets the target you can safely shrink from the left to find the shortest window ending here.

New words, made simpleKnow these before the algorithm

Running sum: The total of the elements currently inside the window.
Shrink step: Removing the leftmost element to test whether a smaller window still meets the target.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

All subarrays

Quadratic; recomputes overlapping sums repeatedly.

Sum every start/end pair and track the shortest meeting the target.

Time O(n^2)Space O(1)

Best choiceTwo-pointer shrinking window

Each element enters and leaves the window once, giving linear time.

Grow right to reach the target, then shrink left to minimize, all in one pass.

Time O(n)Space O(1)

Prefix sums + binary search

Correct and useful when values can be negative, but heavier than needed here.

Build prefix sums and binary-search the shortest qualifying end for each start.

Time O(n log n)Space O(n)

The rule we keep true

Invariant

The running sum always equals the sum of nums[left..right], and after each shrink loop the window is the shortest one ending at right that still reaches (before the last removal) the target.

Why this is correct

Reasoning

With only positive numbers, the window sum is monotonic in its endpoints: extending right can only increase it and shrinking left can only decrease it. So once the target is met we shrink greedily until it is barely met, guaranteeing the minimal window for that right endpoint; scanning all right endpoints yields the global minimum.

The algorithm in three movesSay these aloud before coding

1Maintain a running sum and a left pointer

window [2,3,1,2] sum 8 -> shrink

2Add each element to the running sum as the right pointer advances

reaches [4,3] sum 7 len 2

3While the sum is >= target, record the window length and shrink from the left

best = 2

4Return the smallest length found, or 0 if none

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readadd 2,3,1,2

2 · Asksum >= 7?

3 · Update statewindow [2,3,1,2] len 4

4 · Resultrecord 4, shrink: drop 2 -> sum 6

Key takeaway

The two-element window [4,3] at indices 4-5 is the shortest run summing to at least 7.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Initialize
left marks the window start, total is the running sum, best holds the shortest length (infinity until found).
2
Lines 6-8Grow right
Add each new element to the running sum.
3
Lines 9-12Shrink while valid
While the sum meets the target, record the length and remove the left element to seek a shorter window.
4
Lines 13Handle no-answer
Return 0 when no window ever reached the target.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

No subarray reaches the target returns 0
A single element >= target returns 1
The entire array is needed returns its length
target equal to one element's value

Common beginner mistakes

Assuming this technique works with negative numbers (it relies on positivity for monotonic sums)
Returning infinity instead of 0 when no window qualifies
Using >= vs > incorrectly (the target is inclusive, so use >=)
Off-by-one when computing window length (right - left + 1)

Check your understanding

Why does the shrink-when-valid strategy require all numbers to be positive?

Minimum Size Subarray Sum

Minimum Size Subarray Sum

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Sliding Window