Minimum Size Subarray Sum
Find the shortest run of consecutive positive numbers whose sum reaches a target, using a sliding window that grows and shrinks, in O(n) time.
Updated Medium read: 6 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Sliding window | O(n) | O(1) |
The problem
Given an array of positive integers and a positive target, find the length of the shortest run of consecutive elements whose sum is at least the target. If no run is large enough, return 0.
numbers = [2, 3, 1, 2, 4, 3], target = 7 → 2 (4 + 3)
numbers = [1, 4, 4], target = 4 → 1 (4 on its own)
numbers = [1, 1, 1, 1, 1, 1, 1, 1], target = 11 → 0 (the whole array is only 8)The sum has to be at least the target, not exactly equal to it.
Approach 1: brute force
From each starting position, keep adding elements until the sum reaches the target, and note how many it took.
JavaScript
function minSubarrayLengthBruteForce(numbers, target) {
let best = Infinity;
for (let start = 0; start < numbers.length; start++) {
let sum = 0;
for (let end = start; end < numbers.length; end++) {
sum += numbers[end];
if (sum >= target) {
best = Math.min(best, end - start + 1);
break;
}
}
}
return best === Infinity ? 0 : best;
}Python
def min_subarray_length_brute_force(numbers, target):
best = float("inf")
for start in range(len(numbers)):
total = 0
for end in range(start, len(numbers)):
total += numbers[end]
if total >= target:
best = min(best, end - start + 1)
break
return 0 if best == float("inf") else bestThe break is safe: once a run from start is large enough, making it longer cannot make it shorter.
Time O(n²) in the worst case, when the sums rarely reach the target. Space O(1).
Approach 2: sliding window
The brute force adds up the same elements again and again. A sliding window keeps one running sum and adjusts it.
Hold a window from start to end:
- Move
endone place to the right and add the new number to the sum. - While the sum is at least the target, the window is a valid answer. Record its length, then remove the number at
startand movestartup, to see whether a shorter window still works. - When the sum drops below the target, go back to step 1.
JavaScript
function minSubarrayLength(numbers, target) {
let best = Infinity;
let start = 0;
let sum = 0;
for (let end = 0; end < numbers.length; end++) {
sum += numbers[end];
while (sum >= target) {
best = Math.min(best, end - start + 1);
sum -= numbers[start];
start++;
}
}
return best === Infinity ? 0 : best;
}Python
def min_subarray_length(numbers, target):
best = float("inf")
start = 0
total = 0
for end, value in enumerate(numbers):
total += value
while total >= target:
best = min(best, end - start + 1)
total -= numbers[start]
start += 1
return 0 if best == float("inf") else bestThis is the mirror image of Longest Substring Without Repeating Characters. There the goal is the longest valid window, so the window shrinks only when it breaks a rule. Here the goal is the shortest, so the window shrinks for as long as it stays valid.
Walkthrough
numbers = [2, 3, 1, 2, 4, 3], target = 7:
| end (value) | Sum after adding | Shrinking | Window left | best |
|---|---|---|---|---|
| 0 (2) | 2 | [2] | none | |
| 1 (3) | 5 | [2, 3] | none | |
| 2 (1) | 6 | [2, 3, 1] | none | |
| 3 (2) | 8 | Length 4 recorded; remove 2, sum 6 | [3, 1, 2] | 4 |
| 4 (4) | 10 | Length 4; remove 3, sum 7. Length 3; remove 1, sum 6 | [2, 4] | 3 |
| 5 (3) | 9 | Length 3; remove 2, sum 7. Length 2; remove 4, sum 3 | [3] | 2 |
The answer is 2, for the window [4, 3].
Time O(n). There is a while inside a for, but the cost is not n². start only ever moves forwards, so across the whole run each element is added to the sum once and removed at most once: about 2n steps in total. Space O(1).
Why the numbers must be positive
The window logic rests on two facts that are only true for positive numbers:
- Adding an element always increases the sum.
- Removing an element always decreases it.
That is why, once the sum falls below the target, there is no point shrinking further, and why a window that is too small can only be fixed by growing it.
With negative numbers allowed, both facts fail. For [5, -3, 5] and a target of 7, the only window that works is the whole array, since [5, -3] sums to 2 and [-3, 5] sums to 2. Shrinking a valid window might make its sum larger, and a window abandoned as too small might have become valid by growing past a negative number. That version of the problem, Shortest Subarray with Sum at Least K, needs prefix sums and a queue instead.
A slower alternative worth knowing
Because every number is positive, the running totals from the start of the array (the prefix sums) are in ascending order. For each start position, the earliest end that reaches the target can therefore be found with binary search over those totals. That costs O(n log n) time and O(n) space, so the sliding window beats it on both counts, but it is a common follow-up question.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(minSubarrayLength([2, 3, 1, 2, 4, 3], 7)); // 2
console.log(minSubarrayLength([1, 1, 1], 11)); // 0Python
print(min_subarray_length([2, 3, 1, 2, 4, 3], 7)) # 2
print(min_subarray_length([1, 1, 1], 11)) # 0The comment after each line is the result you should see.
Common mistakes
- Using
ifinstead ofwhileto shrink. One new number can make room to drop several from the front, as rows 4 and 5 of the walkthrough show. - Recording the length after shrinking. The length must be noted while the window is still valid, before the front element is removed.
- Returning
Infinity. If no window ever reaches the target, the answer is0. - Checking for a sum equal to the target. The condition is "at least", so
>=. - Using this on arrays with negative numbers. The method silently gives wrong answers there.
Original problem: LeetCode 209: Minimum Size Subarray Sum