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]
0
2
1
3
2
1
3
2
4
4
5
3
Window [2, 3, 1, 2] sum is 8 >= 7. Valid! Record length 4. Shrinking: drop 2.
0
2
1
3
left
2
1
3
2
4
4
right
5
3
Slide: add 4. Window [3, 1, 2, 4] sum is 10 >= 7. Valid! Min len stays 4. Shrinking: drop 3.
0
2
1
3
2
1
left
3
2
4
4
right
5
3
Shrunk: Window [1, 2, 4] sum is 7 >= 7. Valid! Record new min len 3. Shrinking: drop 1.
0
2
1
3
2
1
3
2
4
4
left
5
3
right
Later slide to 3. Window [4, 3] sum is 7 >= 7. Valid! Record new min len 2. Shrinking: drop 4.

Final Result: 2

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

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.

O(N²) Brute Force
→
O(N log N) Prefix + Binary Search
→
O(N) Variable Sliding Window