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.
+16 hidden tests on Submit
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
The values are all positive, so extending a subarray always raises its sum and cutting it always lowers it. That one fact powers both fast solutions. Prefix sums become a sorted list, so a binary search finds where a sum first reaches target. Better still, the best end never moves left when the start moves right, so a single 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 index and add values one by one going right. The first time the running sum reaches target, you have the shortest subarray that begins at that start: every shorter one stopped earlier and its sum was still too small. So record its length, stop extending, and move to the next start. The answer is the smallest length over all starts.
With target = 15 and [4, 2, 9, 3, 7, 1, 5], start 0 sums 4, 6, 15 and stops at length 3. Start 1 sums 2, 11, 14, 21 and stops at length 4. Start 2 sums 9, 12, 19, length 3 again. No start does better than 3.
The trouble comes when the target is hard to reach. If no subarray reaches it, every start runs to the end of the array: n(n+1)/2 additions, which is 2 × 10^8 for n = 2 × 10^4. Each start also recomputes sums the previous start already had.
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 then prefix[end] - prefix[start]. For a fixed start you want the smallest end with prefix[end] ≥ prefix[start] + target.
Every value is positive, so prefix is strictly increasing, and the first position where it reaches a value is a binary search away. For [4, 2, 9, 3, 7, 1, 5], 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 nums[2..4] = 9, 3, 7, length 3.
If even prefix[n] is below what a start needs, no end works for it, and none works for any later start either, since prefix[start] only grows. Stop there. That is n binary searches, O(n log n) time, plus O(n) for the prefix array. The largest value compared is 2 × 10^8 + 10^9, which fits in a 32-bit integer.
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
Keep a window nums[left..right] and its sum. Move right one step at a time and add the new value. While the sum is at least target, the window is a candidate: record its length, then drop nums[left] and move left forward to see if a shorter window still works.
Why can left leave for good? When the window nums[left..right] first reaches target, the smaller window nums[left..right-1] did not, because the loop would have shrunk it at the previous step. So right is the earliest end for this start, and any later end only gives a longer subarray. The start has given its best answer. This argument needs positive values: with a negative number, a longer window could have a larger sum later on.
On target = 15 and [4, 2, 9, 3, 7, 1, 5]: the sum climbs 4, 6, 15, so length 3 is recorded and 4 leaves (11). Adding 3 gives 14, adding 7 gives 21: record length 4, drop 2 (19), record length 3, drop 9 (10). Adding 1 and 5 gives 16: record length 4, drop 3 (13). The answer is 3.
The while loop sits inside the for loop, yet each index enters the window once and leaves it once, so the total work is O(n). Only three numbers are stored, which is 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
Most bugs sit in the shrinking step and in the value you return when nothing reaches target.
- 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]of length 1 is never measured. A loop keeps removing while the sum is still enough. - Recording the length after removing
nums[left]instead of before. The window you measure must be the one whose sum reachedtarget. - Comparing with
>instead of≥. A subarray whose sum equalstargetcounts:[3, 3, 3]withtarget = 9has answer 3, not 0. - Returning the sentinel. If you start
bestatn+1or infinity, convert it to 0 when nothing reachedtarget. - Reusing the window on arrays with zeros or negatives. It relies on every value being positive; this problem guarantees that, but variants do not.
Frequently asked questions4
What is the time complexity of Minimum Size Subarray Sum?
The sliding window solution runs in O(n) time and O(1) space. The inner loop looks like it could make it quadratic, but left only moves forward, so across the whole run it advances at most n times. The prefix sum version is O(n log n), and checking every start is O(n²).
Why does the sliding window need positive numbers?
Shrinking the window has to lower its sum and growing it has to raise it, or dropping the left element could throw away the start of the answer. With negative numbers that order breaks. The usual fix is prefix sums with a monotonic deque of candidate starts, which still runs in O(n).
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 shows a second use of positive values: the prefix sums are sorted, so a binary search finds where a running total first crosses a threshold. That tool comes back in other problems, such as picking 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. If you need an exact sum instead, the window still works for positive values: shrink while the sum is above the target, and record a length only when it is equal.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def minSubArrayLen(target, nums):
# Write code hereCase 1
Case 2
Case 3
Input
target = 15 nums = [4, 2, 9, 3, 7, 1, 5]
Expected
3