Minimum Size Subarray Sum
You get a positive integer target and an array nums of positive integers. Find the shortest subarray (a run of neighbouring elements) whose sum is at least target, and return its length. If no subarray reaches target, return 0.
Function
- targetinteger
- the sum a subarray must reach or pass
- numsinteger-array
- the array of positive integers
- Returnsinteger
- the length of the shortest subarray with sum at least target, or 0 if none exists
Constraints
1 ≤ target ≤ 1091 ≤ nums.length ≤ 2 × 1041 ≤ nums[i] ≤ 104
Examples
- Input
- target = 15nums = [4, 2, 9, 3, 7, 1, 5]
- Output
- 3
- Explanation
- No two neighbours reach 15: the largest pair is 9 + 3 = 12. Three do: 4 + 2 + 9 = 15 and 9 + 3 + 7 = 19, so the answer is 3.
- Input
- target = 11nums = [1, 2, 3, 4]
- Output
- 0
- Explanation
- The whole array adds up to 10, less than 11, so no subarray reaches the target and the answer is 0.
- Input
- target = 8nums = [3, 8, 2]
- Output
- 1
- Explanation
- The value 8 reaches the target by itself, and no subarray is shorter than one element.
Follow-up
How would you solve it if nums could also hold zeros and negative numbers, where the sliding window no longer works?
Hints
Open them one at a time. Each one gives away a little more.
All values are positive. What happens to the sum of a subarray when you add one more element on the right, and when you remove one from the left?
Keep a window
nums[left..right]and its sum. Grow it on the right until the sum reachestarget. Then the window is a candidate, and you can try to make it shorter.While the sum is at least
target, record the window's length and dropnums[left]. Both edges only move to the right, so every element enters and leaves the window once.
Solution
Every value is positive, so extending a subarray raises its sum and cutting it lowers it. The best end for a start therefore never moves left as the start moves right, and one window that grows on the right and shrinks on the left finds the answer in one pass.
Extend from every start
Correct, but does not finish on the largest tests
Intuition
Fix a start and add values going right. The first time the running sum reaches target, you have the shortest subarray from that start, because every shorter one had a smaller sum. Record its length and move to the next start; the answer is the smallest length over all starts.
When no subarray reaches the target, every start runs to the end of the array: n(n+1)/2 additions, about 2 × 10^8 for n = 2 × 10^4.
Algorithm
- Set
bestto 0, meaning nothing found yet. - For each start index, set a running sum to 0.
- Move an end index right from the start, adding
nums[end]to the sum. - When the sum reaches
target, keepend-start+1if it beatsbest, and stop extending this start. - Return
best.
def minSubArrayLen(target, nums):
n = len(nums)
best = 0 # 0 means no subarray found yet
for start in range(n):
total = 0
for end in range(start, n):
total += nums[end]
if total >= target:
# The shortest subarray from this start ends here
if best == 0 or end - start + 1 < best:
best = end - start + 1
break
return bestPrefix sums and binary search
Intuition
Let prefix[k] be the sum of the first k values, with prefix[0] = 0. The sum of nums[start..end-1] is prefix[end] - prefix[start], so for a fixed start you want the smallest end with prefix[end] ≥ prefix[start] + target. Positive values make prefix strictly increasing, so a binary search finds that end.
In the first example prefix is [0, 4, 6, 15, 18, 25, 26, 31]. From start 2 you need 6 + 15 = 21; the first prefix at least 21 is 25 at index 5, so the window is 9, 3, 7, length 3.
If prefix[n] is below what a start needs, no later start succeeds either, so you stop. That is n binary searches: O(n log n) time and O(n) space.
Algorithm
- Build
prefixof lengthn+1, withprefix[k+1] = prefix[k] + nums[k]. - For each start, compute
need = prefix[start] + target. - If
prefix[n] < need, stop: no later start can succeed. - Binary search positions
start+1tonfor the firstendwithprefix[end] ≥ need, and keepend-startif it is the shortest so far. - Return the shortest length, or 0 if no start succeeded.
from bisect import bisect_left
def minSubArrayLen(target, nums):
n = len(nums)
# prefix[k] is the sum of the first k values; it only grows
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
best = 0
for start in range(n):
need = prefix[start] + target
if prefix[n] < need:
break # no window from here on can reach target
# The first end with prefix[end] >= need closes the shortest window
end = bisect_left(prefix, need, start + 1)
if best == 0 or end - start < best:
best = end - start
return bestSliding window
Intuition
Dropping a start for good is safe. When the window nums[left..right] first reaches target, the window ending at right-1 did not, or the loop would have shrunk it a step earlier. So right is the earliest end for this start, and later ends only give longer subarrays. Record the length, drop nums[left], and keep shrinking while the sum still reaches target.
In the first example the sum climbs 4, 6, 15: record 3 and drop 4. Adding 3 and 7 gives 21: record 4, drop 2 (19), record 3, drop 9 (10). Nothing later beats 3.
Each index enters the window once and leaves it once, so the nested loops do O(n) work in total, with O(1) space.
Algorithm
- Set
left = 0,total = 0andbest = 0. - For each
right, addnums[right]tototal. - While
total ≥ target, keepright-left+1if it beatsbest, subtractnums[left]and moveleftone step right. - Return
best, which is still 0 if the sum never reachedtarget.
def minSubArrayLen(target, nums):
best = 0 # 0 means no window found yet
total = 0 # sum of nums[left .. right]
left = 0
for right in range(len(nums)):
total += nums[right]
# Shrink while the window still reaches target
while total >= target:
if best == 0 or right - left + 1 < best:
best = right - left + 1
total -= nums[left]
left += 1
return best
Pitfalls and edge cases
- Shrinking with
ifinstead ofwhile. Fortarget = 12and[1, 1, 2, 3, 12], adding 12 makes the sum 19; anifrecords length 5, removes one value and moves on, so the window[12]is never measured. - Recording the length after removing
nums[left]. You must measure the window whose sum reachedtarget. - Comparing with
>instead of≥.[3, 3, 3]withtarget = 9has answer 3, not 0. - Returning the sentinel. If
beststarts atn+1or infinity, return 0 when nothing reachedtarget, as in the second example.
Frequently asked questions4
What is the time complexity of Minimum Size Subarray Sum?
The sliding window runs in O(n) time and O(1) space. The inner loop looks quadratic, but left only moves forward, so it advances at most n times in the whole run. The prefix sum version is O(n log n), and trying every start is O(n²).
Why does the sliding window need positive numbers?
The window shrinks only while its sum reaches target, which is right when dropping a value can only lower the sum. With a negative value, dropping it raises the sum. For [5, -10, 20] and target = 15, the window stops at -10, 20 with sum 10 and never measures [20], length 1.
Why learn the O(n log n) prefix sum solution if O(n) exists?
Interviewers often ask for it after the O(n) answer. It uses positivity in a second way: the prefix sums are sorted, so a binary search finds where a running total first crosses a threshold. The same tool picks an index at random in proportion to its weight.
Does the subarray have to add up to exactly target?
No. Any sum greater than or equal to target counts. With target = 15, the window 9, 3, 7 adds up to 19 and still has length 3.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def minSubArrayLen(target, nums):
# Write code hereTest #1
Test #2
Test #3
Arguments
target = 15 nums = [4, 2, 9, 3, 7, 1, 5]
Expected Output
3