Minimum Size Subarray Sum

Given an array of positive integers nums and a target sum, return the minimal length of a contiguous subarray whose sum is at least the target. If there is no such subarray, return 0.

Because all numbers are positive, a sliding window works in O(n).

Why this is worth learning

Positivity makes removing the leftmost number decrease the sum. That monotonic fact, not merely contiguity, makes a one-way window sufficient.

Before coding: one-minute experiment

For target=7 and nums=[2,3,1,2,4,3], what final two-element window proves the answer?

Function signature

func MinSubArrayLen(target int, nums []int) int

Inputs / outputs

• target: required minimum sum.
• nums: slice of positive integers.
• Return: minimal subarray length, or 0 if none.

Example

nums = [2,3,1,2,4,3], target = 7
Output: 2

Reason: [4,3] is the shortest window with sum >= 7.

Constraints

• 0 <= len(nums) <= 100_000
• 1 <= nums[i] <= 1_000_000_000
• 1 <= target <= 1_000_000_000

Core idea (near-solution)

Use a sliding window [l, r] with a running sum.

• Expand r to increase the sum.
• When the sum is >= target, shrink from the left to find the minimal window.

Invariant: the sum always equals the elements inside the current window.

Algorithm (step-by-step)

1. Initialize l = 0, sum = 0, best = +infinity.
2. For each r from 0 to len(nums)-1:
   • Add nums[r] to sum.
   • While sum >= target:
     • Update best = min(best, r-l+1).
     • Subtract nums[l] from sum and increment l.
3. If best was never updated, return 0; otherwise return best.

Correctness sketch

For each right endpoint, extend the current sum and repeatedly remove leftmost values while the sum meets target. Record each valid length before removing a value. The last valid window encountered is the shortest with that right endpoint. A previously removed start never needs reconsideration: any future window retaining it would be longer than a valid window already recorded. Conversely, if the sum is below target, further shrinking cannot make it valid because all numbers are positive. Every endpoint is processed and neither pointer moves backward, so the minimum recorded length is globally optimal; no recorded window means return zero.

Trace (hand walkthrough)

Example input:
nums = [2,3,1,2,4,3], target = 7
Output: 2

Reason: [4,3] is the shortest window with sum >= 7.

Walk:
- r=0 sum=2; r=1 sum=5; r=2 sum=6
- r=3 sum=8 >=7 -> min=4, shrink: drop 2 -> sum=6, l=1
- r=4 sum=10 >=7 -> min=4, drop 3 -> sum=7, l=2 -> min=3; drop 1 -> sum=6, l=3
- r=5 sum=9 >=7 -> min=3, drop 2 -> sum=7, l=4 -> min=2; drop 4 -> sum=3

Pitfalls to avoid

• Forgetting to shrink while sum >= target (must be a loop, not an if).
• Using this approach if numbers can be negative (it breaks the invariant).

Debugging lens

Record the answer before subtracting the leaving value. Use an empty array, no solution, and a single-element solution. Negative numbers would invalidate the shrinking proof and are not accepted input.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• After each shrink loop, sum < target. Adding the next value therefore gives sum < target + 1_000_000_000 <= 2_000_000_000, so this running window sum fits signed 32-bit arithmetic under the stated bounds. A full-array prefix sum has a different bound.
• Track the smallest window; return 0 if no valid window.

Reconstruction checkpoint

For target=7 and nums=[2,3,1,2,4,3], what final two-element window proves the answer?

Return to Sliding Window · Module quiz