Minimum Size Subarray Sum
Problem statement
You are given a positive integer target and a list nums of positive integers. Find the shortest block of neighbouring values in nums whose sum is at least target, and return the length of that block. If no block reaches target, return 0.
Examples
Example 1
Input: target = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2
Explanation: The block [4, 3] sums to 7 and has length 2. No single value reaches 7, so 2 is the shortest.
Example 2
Input: target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1]
Output: 0
Explanation: The whole list only sums to 8, which is less than 11, so no block works.
Hints
Approach
Optimal: Sliding window
Intuition
Think of a stretchy window over the list. Grow it on the right until its sum reaches target. Now it is a valid block, so write down its length, then shrink it from the left to see if a shorter block still works. Shrinking is safe only because the numbers are positive: removing a value always lowers the sum, so once the sum drops below target, no shorter window ending at this right can work and we move on. This is faster than the prefix approach because it needs no extra array and no binary search.
Steps
- Set
left = 0,total = 0,best = 0. - For each
right, addnums[right]tototal. - While
total >= target: recordright - left + 1if it is the best so far, subtractnums[left]fromtotal, and moveleftone step right. - Return
best.
Dry run
target = 7, nums = [2, 3, 1, 2, 4, 3]
| right | added | total after adding | shrinking | best |
|---|---|---|---|---|
| 0 | 2 | 2 | none | 0 |
| 1 | 3 | 5 | none | 0 |
| 2 | 1 | 6 | none | 0 |
| 3 | 2 | 8 | length 4, drop 2 → total 6 | 4 |
| 4 | 4 | 10 | length 4, drop 3 → 7; length 3, drop 1 → 6 | 3 |
| 5 | 3 | 9 | length 3, drop 2 → 7; length 2, drop 4 → 3 | 2 |
Edge cases: if the sum never reaches target, the while never runs and best stays 0. A single value that is already at least target gives length 1.
Complexity
Time O(n) - The `right` pointer moves forward n times in total. The `left` pointer only moves forward and never passes `right`, so it also moves at most n times. The inner `while` loop looks nested, but across the whole run it adds at most n steps.
Space O(1) - We keep the window sum, two pointers and the best length. The window is never stored as a separate list. Memory does not grow with the input.
class Solution:
def minSubArrayLen(self, target: int, nums: list[int]) -> int:
left = 0
total = 0
best = 0
for right, x in enumerate(nums):
total += x
while total >= target:
length = right - left + 1
if best == 0 or length < best:
best = length
total -= nums[left] # try a shorter window
left += 1
return best
if __name__ == "__main__":
print(Solution().minSubArrayLen(7, [2, 3, 1, 2, 4, 3]))
print(Solution().minSubArrayLen(11, [1, 1, 1, 1, 1, 1, 1, 1]))RecapThe whole problem in a few lines, for the night before
- Spot it: shortest contiguous piece whose sum is at least a target, all numbers positive
- Idea: sliding window; grow the right end, and while the sum is at least the target, record the length and shrink from the left
- Cost: O(n) time, O(1) space
- Trap: return 0 when no window works; shrinking only works because the numbers are positive
Interview follow-ups
Return the start and end positions of the shortest block.
Store two more numbers,
best_leftandbest_right. Each time the window sum reachestargetand the window is shorter thanbest, copy the currentleftandrightinto them before you shrink the window. At the end, return the pair, or an empty result if no block reachedtarget. Time stays O(n) and space stays O(1).Handle lists that may contain negative numbers.
The sliding window breaks, because removing a value from the left can now increase the sum. Switch to prefix sums with a monotonic deque of positions. For each position
j, while the front positionigivesprefix[j] - prefix[i] >= target, recordj - iand pop the front. Before pushingj, pop from the back while the back prefix is greater than or equal toprefix[j], sincejis a later and no worse start. This runs in O(n) time with O(n) space.
Frequently asked questions
The left pointer only moves forward and never passes right. Across the whole run it moves at most n times in total. So the inner loop adds O(n) work overall, not O(n) per value. Counting the total moves of both pointers, not the loop nesting, is the right way to measure it.
No. With negatives, dropping a value from the left can increase the sum, so the shrink step can miss answers. The prefix array is also no longer sorted, so the binary search breaks. That version needs a monotonic deque over the prefix sums, shown in the follow-ups.
The problem defines 0 as the "no block" answer, since a real block always has length at least 1. In the code, best == 0 also means "nothing found yet", which is why the update checks best == 0 or length < best.
It answers questions like "what is the shortest stretch of consecutive minutes in which errors reached a threshold?" or "the fewest consecutive log batches that add up to 1 GB". Counts and sizes are never negative, which is exactly the condition the window needs.
