Algorithm

Minimum Size Subarray Sum

Sliding Window Pattern

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.

CONSTRAINTS
  • 1 <= target <= 10⁹
  • 1 <= nums.length <= 10⁵
  • 1 <= nums[i] <= 10⁴
EXAMPLE 1
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
The subarray [4,3] has sum 7 and length 2. This is the minimum length.
EXAMPLE 2
Input: target = 4, nums = [1,4,4]
Output: 1
A single element 4 satisfies sum >= 4. Minimum length is 1.
EXAMPLE 3
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Total sum is 8, which is less than target 11. No valid subarray exists. Return 0.
What should be returned if no subarray meets the target?
Return 0. If you complete the search and shortest never changes from infinity, it means even the entire array doesn't reach the target.
Are there negative numbers?
No, all numbers are positive. This is critical because it guarantees that adding elements always increases the sum (monotonicity).
Is the window size fixed?
No, this is a Variable Sliding Window. We expand and shrink the window to find the optimal size.

This 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.

The all-subarrays way

Try every start i, extend until the running sum hits target, note the length, and keep the smallest.

python
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 found

That 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.

Why the window is even allowed here

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).

Shrink while still valid — the shortest-window shape

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.

python
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 best
Crucial Noterecord the length before subtracting nums[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.
Worked Example:target = 7, nums = [2, 3, 1, 2, 4, 3]
- Expand to [2,3,1,2], sum 8 ≥ 7. Record len 4. Shrink: drop 2 → [3,1,2] sum 6, invalid.
- Expand to [3,1,2,4], sum 10 ≥ 7. Record len 4 (no better). Shrink: drop 3 → [1,2,4] sum 7 ≥ 7, record len 3. Shrink: drop 1 → [2,4] sum 6, invalid.
- Expand to [2,4,3], sum 9 ≥ 7. Record len 3. Shrink: drop 2 → [4,3] sum 7 ≥ 7, record len 2. Shrink: drop 4 → [3] sum 3, invalid.
- Answer: 2 (the window [4,3]).

If the whole array never reaches target — say target 11, nums all 1s summing to 8 — best stays infinity and we return 0.

How it maps onto the pattern

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.

Interactive Strategy Visualization

Min Size Subarray

Target: 7
Greedy Shrinking
2
0
3
1
1
2
2
3
4
4
3
5
Current Sum
2
Min Length So Far
N/A
O(N²) Brute Force
O(N log N) Prefix + Binary Search
O(N) Variable Sliding Window