Minimum Size Subarray Sum
Problem Statement
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is at least target. If no such subarray exists, return 0.
Input
A positive integer target and an array of positive integers nums.
Output
An integer: the length of the shortest contiguous subarray with sum at least target, or 0 if none exists.
Constraints
- •
1 <= target <= 10^9 - •
1 <= nums.length <= 10^5 - •
1 <= nums[i] <= 10^4
Examples
Example 1
target = 7, nums = [2,3,1,2,4,3]
2Example 2
target = 4, nums = [1,4,4]
1Example 3
target = 11, nums = [1,1,1,1,1,1,1,1]
0Learning Objectives
- Recognise a shortest-valid variable window over positive numbers.
- Use positivity to justify shrinking while the current sum remains at least the target.
- Record the answer before removing the leftmost element from a valid window.
- Distinguish this linear window from prefix-sum binary search alternatives.
Intuition
Pattern Identification
This is a shortest-valid variable-window problem. The window condition is sum >= target, and all numbers are positive. That positivity is what makes the window monotone: expanding right never decreases the sum, and shrinking left never increases it.
The expand and shrink invariant is: expand until the window is valid, then shrink as much as possible while it stays valid. Every time the sum reaches the target, the current window is a candidate answer. Shrinking immediately tests whether a shorter candidate with the same right boundary exists.
Common mistakes
- ×Using a sliding window when negative numbers are allowed; the monotone sum property would break.
- ×Updating the best length only after shrinking, which can miss the current valid window.
- ×Stopping after finding the first valid window instead of continuing to find a shorter one.
- ×Returning the sentinel length instead of **0** when no valid subarray exists.
Algorithm Explanation
Window setup
Keep left, right, the current window sum, and bestLength. The window contains positive numbers from left through right. Because every value is positive, moving left rightward makes the sum smaller in a predictable way.
Window visualization
For target = 7 and nums = [2,3,1,2,4,3], expand until the sum first reaches 8 at window [2,3,1,2]. Record length 4, then shrink from the left: removing 2 leaves sum 6, so this right boundary cannot produce a shorter valid window. Continue expanding to include 4, which gives sum 10 over [3,1,2,4]. Now repeated shrinking finds [2,4] with length 2 before the sum drops below 7. The final 3 confirms another length 2 window [4,3].
Algorithm
- Set left = 0, sum = 0, and bestLength to a sentinel larger than the array length.
- For each right index, add nums[right] to sum.
- While sum >= target, update bestLength with the current length.
- Subtract nums[left] and increment left to search for a shorter valid window.
- After the scan, return 0 if the sentinel was never changed; otherwise return bestLength.
Solutions
Solution: Shortest valid positive-sum window
Since every element is positive, once a window reaches the target we can safely remove elements from the left until it becomes invalid. That finds the shortest valid window ending at each right index.
Step-by-step
- Expand the right boundary and add each number to the running sum.
- Whenever the sum is at least target, record the current window length.
- Remove nums[left] and move left forward to test a shorter window with the same right boundary.
- Repeat the shrink step until the sum falls below target.
- Return the best recorded length, or 0 if no valid window was recorded.
O(n)
O(1)
Both pointers move from left to right at most once.
Java implementation
Dry Run
Sample input
target = 7, nums = [2,3,1,2,4,3]. Track the positive-sum window and update the best length before each shrink.
| step | right value | left before shrinking | sum after expand | shrink actions | best length |
|---|---|---|---|---|---|
| 1 | 2 at 0 | 0 | 2 | sum < 7, keep expanding | none |
| 2 | 3 at 1 | 0 | 5 | sum < 7, keep expanding | none |
| 3 | 1 at 2 | 0 | 6 | sum < 7, keep expanding | none |
| 4 | 2 at 3 | 0 | 8 | record 4, remove 2, sum becomes 6 | 4 |
| 5 | 4 at 4 | 1 | 10 | record 4, remove 3; record 3, remove 1; record 2, remove 2 | 2 |
| 6 | 3 at 5 | 4 | 7 | record 2, remove 4, sum becomes 3 | 2 |
The shortest valid window has length 2, achieved by [2,4] and [4,3].
Interview Tips
Call out that positivity is the reason the two-pointer window works. If the interviewer allows negative numbers, this exact shrink rule is no longer safe and you need a prefix-sum plus monotonic deque style approach for related variants. In this problem, record the length before subtracting from the left because the current window is valid at that moment.
Likely follow-ups
- What changes if **nums** can contain negative values?
- How would you return the start and end indices of the shortest valid subarray?
- How would you solve many target queries over the same positive array?
- Can you solve it with prefix sums and binary search, and when would that be useful?
Similar Problems
Key Takeaways
- Shortest-valid windows record an answer as soon as the window becomes valid.
- Positive numbers make sum-based shrinking safe and monotone.
- The inner while loop finds the shortest valid window for the current **right** boundary.
- Return **0** when no window ever reaches the target.