#209
Minimum Size Subarray Sum
Medium Variable window (shrink while valid)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
All numbers are positive. Return the length of the shortest contiguous subarray whose sum is at least target, or 0 if none.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the shortest piece (positive numbers) with sum ≥ target.
Why this works: grow until the sum is big enough, then shrink from the left as long as it stays big enough, recording lengths.
Example: target 7, [2, 3, 1, 2, 4, 3]
2+3+1+2 = 8 ≥ 7 → length 4, drop 2 → 6+4 → 10 → length 4, drop 3 → 7 → length 3, drop 1 → 6+3 → 9 → length 3, drop 2 → 7 → length 2 ✓answer 2
✦Hints open one at a time
Expand the window until the sum reaches target.
Then shrink from the left as long as it still reaches target, recording lengths.
↗Approach
Because values are positive, adding grows the sum and removing shrinks it. Expand right; while sum >= target, update the best length and remove nums[left].
</>Solution (Java)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0, best = Integer.MAX_VALUE;
for (int r = 0; r < nums.length; r++) {
sum += nums[r];
while (sum >= target) { // shrink while still valid
best = Math.min(best, r - left + 1);
sum -= nums[left++];
}
}
return best == Integer.MAX_VALUE ? 0 : best;
}
}!Common mistake
Using "if" instead of "while" for shrinking — you'd miss shorter windows.
Complexity
- Time: O(n) — each index enters and leaves once.
- Space: O(1).
Topic: Sliding Window
🎬 Episode 10: video coming soon