Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
- 1 <= target <= 10⁹
- 1 <= nums.length <= 10⁵
- 1 <= nums[i] <= 10⁴
target = 7, nums = [2,3,1,2,4,3]2target = 4, nums = [1,4,4]1target = 11, nums = [1,1,1,1,1,1,1,1]0This is the same Variable Sliding Window from Longest Substring Without Repeating Characters, but flipped to its other shape. There we wanted the longest valid window; here we want the shortest contiguous block whose sum reaches target. If no block ever reaches it, return 0.
Try every start i, extend until the running sum hits target, note the length, and keep the smallest.
best = infinity
for i in range(len(nums)):
total = 0
for j in range(i, len(nums)):
total += nums[j]
if total >= target:
best = min(best, j - i + 1)
break # shortest for this start foundThat re-adds elements from scratch for every start — O(N²). The overlap between consecutive starts is thrown away, exactly the waste the sliding window exists to remove.
The window needs the rule to move in one direction at the edges, and here the enabling property is stated right in the constraints: every number is positive. So adding an element on the right can only raise the sum (toward valid), and removing one on the left can only lower it (toward invalid). That is the one-directional behaviour the pattern demands — and it is precisely why negatives would wreck it (more on that below).
Because we want the shortest qualifying window, the move is different from the longest-window template: expand right to gather sum, and the instant the window is valid (sum ≥ target), record the length and then keep shrinking from the left while it stays valid, hunting for something even tighter. In the longest shape you shrink only when forced and record after; in the shortest shape you shrink greedily while allowed and record on the way.
best = infinity
total = 0
left = 0
for right in range(len(nums)):
total += nums[right] # expand
while total >= target: # still valid - try to tighten
best = min(best, right - left + 1) # record BEFORE shrinking
total -= nums[left]
left += 1
return 0 if best == infinity else bestnums[left], while the window is still valid — the step that shrinks it may push the sum under target, and a window measured after that would be a losing (invalid) one. Each element enters once and leaves once, so the nested while is still one linear pass overall.If the whole array never reaches target — say target 11, nums all 1s summing to 8 — best stays infinity and we return 0.
Filling the four slots: (a) invalid = sum < target (so we shrink while sum ≥ target); (b) expand adds nums[right] to a running sum; (c) shrinking subtracts nums[left]; (d) record the minimum width, and do it inside the shrink loop while still valid. The single thing that flips this from Longest Substring's shape is when you record — valid-and-shrinking here, versus valid-after-fixing there.
Where it breaks: allow negative numbers and the property collapses — adding an element could now lower the sum and removing one could raise it, so a window that falls short might be rescued by extending further left, and left can no longer march forward blindly. "Shortest subarray with sum ≥ target" with negatives is a genuinely harder problem (prefix sums plus a monotonic deque), not a plain sliding window. The positivity in the constraints is not decoration — it is the license to use this pattern.
Min Size Subarray
Monotonicity Property
Because all numbers are positive, the sum is monotonic. Adding elements increases the sum, and removing decreases it. This allows us to greedily shrink valid windows.
Step-by-Step Logic
Step 1: First element 2 < 7. Window too small, must expand right.