Minimum Size Subarray Sum (LeetCode 209)
nums is an array of positive integers, and target is a positive integer. Among all contiguous subarrays whose sum reaches at least target, find the shortest one and return its length — or 0 if no subarray sums that high.
Worked Examples
target = 7, nums = [2,3,1,2,4,3]2target = 4, nums = [1,4,4]14 already reaches the target, so the answer is 1.target = 11, nums = [1,1,1,1,1,1,1,1]08, which is below 11, so no subarray works.⚖️Formal Constraints & Bounds
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
Core Insight
Both left and right pointers only move forward. Each element is added once and removed at most once, achieving O(N) total runtime.
Real-World Scenario & Production Applications
Network packet rate limiting and video streaming buffer window management use sliding windows to track cumulative bandwidth usage.
Subproblems & Recurrence Decomposition3 Phases
Grow the window by advancing right and accumulating window_sum += nums[right] until the sum meets or exceeds target.
window_sum += nums[right]Step-by-Step Execution Trace Table
| Step | Action | left | right | window_sum | min_len | Pedagogical Explanation |
|---|---|---|---|---|---|---|
| 1 | 🟢 GROW (nums[0]=2) | 0 | 0 | 2 | Sum = 2 < 7; window invalid. Advance right. | |
| 2 | 🟢 GROW (nums[1]=3) | 0 | 1 | 5 | Sum = 5 < 7; advance right. | |
| 3 | 🟢 GROW (nums[2]=1) | 0 | 2 | 6 | Sum = 6 < 7; advance right. | |
| 4 | 🟢 GROW (nums[3]=2) | 0 | 3 | 8 | Sum = 8 7; window becomes valid! | |
| 5 | ✅ RECORD & 🔴 SHRINK | 0 1 | 3 | 8 6 | 4 | Record min_len = min(inf, 4) = 4. Drop nums[0]=2. Sum drops to 6 < 7. |
| 6 | 🟢 GROW (nums[4]=4) | 1 | 4 | 10 | 4 | Add nums[4]=4. Sum = 10 7; valid! |
| 7 | ✅ RECORD & 🔴 SHRINK | 1 2 | 4 | 10 7 | 4 | Record len = 4 (no gain). Drop nums[1]=3. Sum = 7 7 (still valid!). |
| 8 | ✅ RECORD & 🔴 SHRINK | 2 3 | 4 | 7 6 | 3 | Record min_len = min(4, 3) = 3. Drop nums[2]=1. Sum = 6 < 7. |
| 9 | 🟢 GROW (nums[5]=3) | 3 | 5 | 9 | 3 | Add nums[5]=3. Sum = 9 7; valid! |
| 10 | ✅ RECORD & 🔴 SHRINK | 3 4 | 5 | 9 7 | 3 | Record len = 3. Drop nums[3]=2. Sum = 7 7 (still valid!). |
| 11 | ✅ RECORD & 🔴 SHRINK | 4 5 | 5 | 7 3 | 2 | Record min_len = min(3, 2) = 2. Drop nums[4]=4. Sum = 3 < 7. |
| 12 | 🏁 DONE | 5 | 5 | 3 | 2 | right reached end. Return minimal length 2. |
| 1 | left = 0 |
| 2 | curr_sum = 0 |
| 3 | min_len = float('inf') |
| 4 | for right in range(len(nums)): |
| 5 | curr_sum += nums[right] |
| 6 | while curr_sum >= target: |
| 7 | min_len = min(min_len, right - left + 1) |
| 8 | curr_sum -= nums[left] |
| 9 | left += 1 |
| 10 | return 0 if min_len == float('inf') else min_len |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Finding the shortest contiguous subarray whose sum meets or exceeds a target value target over an array of positive integers is the archetype of the Dynamic Shrinking Sliding Window. In brute force, evaluating every pair (i, j) requires checks. Because all elements are strictly positive, adding an element strictly increases the sum (monotonic expansion), and removing an element strictly decreases the sum (monotonic contraction). This enables a two-pointer window that never backtracks.
🏟️ The Analogy: The Accordion on the Escalator
Picture playing an accordion on a moving escalator. The right hand pulls the bellows open to suck in air (increase the sum) until the chord sounds (sum target). Once the chord is loud enough, the left hand squeezes the bellows closed (incrementing left) to see how small the instrument can be made while keeping the tone audible. Once the sound drops below the threshold, the right hand pulls again.
🔑 Why It Works
Why is this despite the nested while loop? Because left only increments and never resets to 0. Across the entire traversal of size , right advances times and left advances at most times. Total operations are strictly bounded by .
Recording answer outside the validity loop: In shortest-window problems (LC 209), the window is valid INSIDE the shrinking loop. You must record
min_len = min(min_len, right - left + 1)inside thewhile current_sum >= target:loop before shrinking.Returning uninitialized sentinel: If no qualifying subarray exists, return
0, not infinity (float('inf')). Always returnmin_len if min_len != float('inf') else 0.Applying sliding window with negative numbers: If
numscontains negative numbers, removingnums[left]can increase the sum, breaking monotonicity. Use prefix sum + monotonic deque for negative inputs.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The shortest subarray whose sum reaches at least target, over an array of positive numbers: the shortest valid window over non-negative values (Shortest Window).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: curr_sum is the sum of nums[left..right]; while curr_sum >= target, record right - left + 1 in min_len and drop nums[left].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Negative numbers: dropping
nums[left]can raisecurr_sum, so the scan misses shorter windows; this needsnums[i] >= 0(LC 209 promises it).Recording
min_lenafter the shrinking loop instead of inside it: by then the window is no longer valid, so the recorded length is one element too short.Returning the
infplaceholder instead of0when no window reachestarget.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"This is a Shortest Window problem. I move right and add nums[right] to curr_sum. As soon as the sum reaches the target, I shrink from the left while it stays valid, recording the length each time, because any longer window with the same start can only be worse. Neither pointer ever moves back, so each element enters and leaves the window at most once:
O(N)time,O(1)space. The trap is negative numbers: then dropping a value can raise the sum and the scan misses answers, which is why this relies on the values being positive. If no window ever reaches the target, I return 0, not infinity."
Complexity & Mathematical Proof
O(N)
Look at the nested-looking loops: outer for right in range(len(nums)): and inner while curr_sum >= target:. Notice the pointer lifecycles: right increments from 0 to N-1 exactly N times. The left pointer only ever increments forward (left += 1) and NEVER resets backward. Across the entire function run, left can advance at most N times total. Total pointer operations = N (right advances) + N (left advances) = 2N, giving amortized O(N) linear time.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative loop with zero recursion frames. Look at memory allocation: We do NOT allocate any arrays, hash tables, or recursion frames. We only maintain four scalar integer variables (left, right, curr_sum, min_len) in CPU memory registers. Auxiliary space is strictly O(1) in-place.
∑ (delta R + delta L) ≤ 2N ⟹ O(N)
Derivation Progression
N iterations
The outer for loop advances right from 0 to N-1, adding nums[right] to curr_sum in O(1) per step.
∑ delta left ≤ N
The inner while loop shrinks the window from the left. Because left only increments and never resets, it advances at most N times total.
N + N = 2N ⟹ O(N)
Total pointer advances across the entire array is bounded by 2N, yielding amortized O(N) time.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative loop with zero recursion frames
O(1) Only scalar integer registers (left, right, curr_sum, min_len)
O(1) Returns minimum subarray length integer
Boundary Best / Worst Cases
: right always scans the whole array; the shrinking loop may do no work at all (nothing reaches target).
.
full array scan.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimal length of contiguous subarray", "sum greater than or equal to target", "positive integers". Monotonic sliding window (grow to satisfy, shrink to optimize).
, , . Strictly time with auxiliary space; on a stream the window needs only the values between left and right, so memory is bounded by the longest window, not by .
On a stream, the answer is only final when the stream ends, so report min_len as a running best rather than a final result.
Minimum Size Subarray Sum (LeetCode 209)
nums is an array of positive integers, and target is a positive integer. Among all contiguous subarrays whose sum reaches at least target, find the shortest one and return its length — or 0 if no subarray sums that high.
Worked Examples
target = 7, nums = [2,3,1,2,4,3]2target = 4, nums = [1,4,4]14 already reaches the target, so the answer is 1.target = 11, nums = [1,1,1,1,1,1,1,1]08, which is below 11, so no subarray works.⚖️Formal Constraints & Bounds
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
Core Insight
Both left and right pointers only move forward. Each element is added once and removed at most once, achieving O(N) total runtime.
Real-World Scenario & Production Applications
Network packet rate limiting and video streaming buffer window management use sliding windows to track cumulative bandwidth usage.
Subproblems & Recurrence Decomposition3 Phases
Grow the window by advancing right and accumulating window_sum += nums[right] until the sum meets or exceeds target.
window_sum += nums[right]Step-by-Step Execution Trace Table
| Step | Action | left | right | window_sum | min_len | Pedagogical Explanation |
|---|---|---|---|---|---|---|
| 1 | 🟢 GROW (nums[0]=2) | 0 | 0 | 2 | Sum = 2 < 7; window invalid. Advance right. | |
| 2 | 🟢 GROW (nums[1]=3) | 0 | 1 | 5 | Sum = 5 < 7; advance right. | |
| 3 | 🟢 GROW (nums[2]=1) | 0 | 2 | 6 | Sum = 6 < 7; advance right. | |
| 4 | 🟢 GROW (nums[3]=2) | 0 | 3 | 8 | Sum = 8 7; window becomes valid! | |
| 5 | ✅ RECORD & 🔴 SHRINK | 0 1 | 3 | 8 6 | 4 | Record min_len = min(inf, 4) = 4. Drop nums[0]=2. Sum drops to 6 < 7. |
| 6 | 🟢 GROW (nums[4]=4) | 1 | 4 | 10 | 4 | Add nums[4]=4. Sum = 10 7; valid! |
| 7 | ✅ RECORD & 🔴 SHRINK | 1 2 | 4 | 10 7 | 4 | Record len = 4 (no gain). Drop nums[1]=3. Sum = 7 7 (still valid!). |
| 8 | ✅ RECORD & 🔴 SHRINK | 2 3 | 4 | 7 6 | 3 | Record min_len = min(4, 3) = 3. Drop nums[2]=1. Sum = 6 < 7. |
| 9 | 🟢 GROW (nums[5]=3) | 3 | 5 | 9 | 3 | Add nums[5]=3. Sum = 9 7; valid! |
| 10 | ✅ RECORD & 🔴 SHRINK | 3 4 | 5 | 9 7 | 3 | Record len = 3. Drop nums[3]=2. Sum = 7 7 (still valid!). |
| 11 | ✅ RECORD & 🔴 SHRINK | 4 5 | 5 | 7 3 | 2 | Record min_len = min(3, 2) = 2. Drop nums[4]=4. Sum = 3 < 7. |
| 12 | 🏁 DONE | 5 | 5 | 3 | 2 | right reached end. Return minimal length 2. |
| 1 | left = 0 |
| 2 | curr_sum = 0 |
| 3 | min_len = float('inf') |
| 4 | for right in range(len(nums)): |
| 5 | curr_sum += nums[right] |
| 6 | while curr_sum >= target: |
| 7 | min_len = min(min_len, right - left + 1) |
| 8 | curr_sum -= nums[left] |
| 9 | left += 1 |
| 10 | return 0 if min_len == float('inf') else min_len |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Finding the shortest contiguous subarray whose sum meets or exceeds a target value target over an array of positive integers is the archetype of the Dynamic Shrinking Sliding Window. In brute force, evaluating every pair (i, j) requires checks. Because all elements are strictly positive, adding an element strictly increases the sum (monotonic expansion), and removing an element strictly decreases the sum (monotonic contraction). This enables a two-pointer window that never backtracks.
🏟️ The Analogy: The Accordion on the Escalator
Picture playing an accordion on a moving escalator. The right hand pulls the bellows open to suck in air (increase the sum) until the chord sounds (sum target). Once the chord is loud enough, the left hand squeezes the bellows closed (incrementing left) to see how small the instrument can be made while keeping the tone audible. Once the sound drops below the threshold, the right hand pulls again.
🔑 Why It Works
Why is this despite the nested while loop? Because left only increments and never resets to 0. Across the entire traversal of size , right advances times and left advances at most times. Total operations are strictly bounded by .
Recording answer outside the validity loop: In shortest-window problems (LC 209), the window is valid INSIDE the shrinking loop. You must record
min_len = min(min_len, right - left + 1)inside thewhile current_sum >= target:loop before shrinking.Returning uninitialized sentinel: If no qualifying subarray exists, return
0, not infinity (float('inf')). Always returnmin_len if min_len != float('inf') else 0.Applying sliding window with negative numbers: If
numscontains negative numbers, removingnums[left]can increase the sum, breaking monotonicity. Use prefix sum + monotonic deque for negative inputs.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The shortest subarray whose sum reaches at least target, over an array of positive numbers: the shortest valid window over non-negative values (Shortest Window).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: curr_sum is the sum of nums[left..right]; while curr_sum >= target, record right - left + 1 in min_len and drop nums[left].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Negative numbers: dropping
nums[left]can raisecurr_sum, so the scan misses shorter windows; this needsnums[i] >= 0(LC 209 promises it).Recording
min_lenafter the shrinking loop instead of inside it: by then the window is no longer valid, so the recorded length is one element too short.Returning the
infplaceholder instead of0when no window reachestarget.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"This is a Shortest Window problem. I move right and add nums[right] to curr_sum. As soon as the sum reaches the target, I shrink from the left while it stays valid, recording the length each time, because any longer window with the same start can only be worse. Neither pointer ever moves back, so each element enters and leaves the window at most once:
O(N)time,O(1)space. The trap is negative numbers: then dropping a value can raise the sum and the scan misses answers, which is why this relies on the values being positive. If no window ever reaches the target, I return 0, not infinity."
Complexity & Mathematical Proof
O(N)
Look at the nested-looking loops: outer for right in range(len(nums)): and inner while curr_sum >= target:. Notice the pointer lifecycles: right increments from 0 to N-1 exactly N times. The left pointer only ever increments forward (left += 1) and NEVER resets backward. Across the entire function run, left can advance at most N times total. Total pointer operations = N (right advances) + N (left advances) = 2N, giving amortized O(N) linear time.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative loop with zero recursion frames. Look at memory allocation: We do NOT allocate any arrays, hash tables, or recursion frames. We only maintain four scalar integer variables (left, right, curr_sum, min_len) in CPU memory registers. Auxiliary space is strictly O(1) in-place.
∑ (delta R + delta L) ≤ 2N ⟹ O(N)
Derivation Progression
N iterations
The outer for loop advances right from 0 to N-1, adding nums[right] to curr_sum in O(1) per step.
∑ delta left ≤ N
The inner while loop shrinks the window from the left. Because left only increments and never resets, it advances at most N times total.
N + N = 2N ⟹ O(N)
Total pointer advances across the entire array is bounded by 2N, yielding amortized O(N) time.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative loop with zero recursion frames
O(1) Only scalar integer registers (left, right, curr_sum, min_len)
O(1) Returns minimum subarray length integer
Boundary Best / Worst Cases
: right always scans the whole array; the shrinking loop may do no work at all (nothing reaches target).
.
full array scan.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimal length of contiguous subarray", "sum greater than or equal to target", "positive integers". Monotonic sliding window (grow to satisfy, shrink to optimize).
, , . Strictly time with auxiliary space; on a stream the window needs only the values between left and right, so memory is bounded by the longest window, not by .
On a stream, the answer is only final when the stream ends, so report min_len as a running best rather than a final result.