Minimum Size Subarray Sum: The Sliding Window
Published Updated Algorithms 10 min read
Find the shortest contiguous subarray whose sum reaches a target, in O(n) and O(1) extra space. Plus the condition that makes the window valid, and what breaks when negatives are allowed.
Given an array of positive integers and a target, find the length of the shortest contiguous subarray whose sum is at least the target. Return 0 when no such subarray exists.
nums = [2, 3, 1, 2, 4, 3], target = 7 -> 2 // [4, 3]
nums = [1, 4, 4], target = 4 -> 1 // [4]
nums = [1, 1, 1, 1], target = 11 -> 0
The brute force is two nested loops over every start and end, which is O(n²). The sliding window gets it to O(n) with no extra space, and the reason it works is worth understanding, because the same reasoning tells you exactly when it stops working.
Why a window is enough
Both pointers only ever move forward. That is the whole trick, and it depends on one property of the input: all values are positive.
With positive values, extending the window to the right can only increase the sum, and shrinking it from the left can only decrease it. So the sum is monotonic in each pointer, and once a window reaching the target has been found, there is no reason to move the left pointer backwards. Anything to the left produces a longer window with a sum that is at least as large, which cannot be a better answer.
That gives the invariant the whole algorithm rests on: the window is shrunk while it still meets
the target. Every position is entered once by right and left once by left, so the total work
is 2n even though the code has nested loops.
The implementation
public int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0;
int best = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
best = Math.min(best, right - left + 1);
sum -= nums[left];
left++;
}
}
return best == Integer.MAX_VALUE ? 0 : best;
}
Three details carry the correctness.
The inner loop is a while, not an if. After removing one element the window may still meet the
target, and every one of those shorter windows is a candidate. An if finds a valid answer and
misses the best one.
The length is recorded before shrinking, because at that moment the window is the smallest valid
one ending at right.
best is seeded with a sentinel rather than 0, since 0 is the answer for “no subarray exists” and
would otherwise win every comparison.
Walking one input
For nums = [2, 3, 1, 2, 4, 3] and target = 7:
| right | value | window | sum | action |
|---|---|---|---|---|
| 0 | 2 | [2] | 2 | below target |
| 1 | 3 | [2,3] | 5 | below target |
| 2 | 1 | [2,3,1] | 6 | below target |
| 3 | 2 | [2,3,1,2] | 8 | valid, length 4, shrink to [3,1,2] sum 6 |
| 4 | 4 | [3,1,2,4] | 10 | valid, length 4, shrink twice to [2,4] sum 6 |
| 5 | 3 | [2,4,3] | 9 | valid, length 3, shrink to [4,3] sum 7, length 2 |
The answer is 2. Note how left advanced from 0 to 4 across the whole run and never went back.
Proving it does not miss the answer
The loop is short enough that it is tempting to accept it on the strength of one worked example. The argument that it is actually correct is short too, and it is the part an interviewer asks for.
Let the optimal answer be the subarray from index a to index b. When right reaches b, the
left pointer is at some index l. Two cases cover everything.
If l <= a, the window from l to b includes the optimal one, so its sum is at least the target,
so the inner loop runs. It keeps shrinking while the sum still meets the target, so it passes
through a and records a length no greater than b - a + 1.
If l > a, then left moved past a at some earlier step. It only moves when the window was valid
before removing an element, so a valid window ending before b and starting at or after a was
already recorded, and that window is no longer than the optimal one.
Either way the recorded best is at most the optimal length, and since every recorded window is genuinely valid it cannot be shorter. The two bounds meet, so the answer is exact.
An off-by-one worth knowing
The window length is right - left + 1, and the + 1 is the single most common bug in this family.
Both indices are inclusive: when left == right the window holds one element, and right - left
would report zero. A quick way to check any window implementation is to run it on a single-element
array whose value already meets the target, where the correct answer is 1.
Complexity
Time is O(n). The outer loop runs n times and the inner while advances left, which can happen at
most n times in total across the entire execution. It is a common mistake to read the nested loops
as O(n²); the bound comes from counting pointer movements, not loop nesting.
Space is O(1). Nothing is stored beyond three integers.
Where the window breaks: negative numbers
Allow negatives and the monotonicity is gone. Extending the window may now decrease the sum, so a window that falls short might reach the target after adding more elements, and shrinking from the left might increase the sum. Neither pointer can be advanced with confidence.
For the variant “shortest subarray with sum at least K” over an array containing negatives, the
sliding window returns wrong answers. The correct approach uses prefix sums with a monotonic deque:
compute prefix[i], and for each i find the largest j < i where prefix[i] - prefix[j] >= K,
maintaining the deque in increasing order of prefix value. That is still O(n) but it is a different
algorithm, and reaching for it is the right call the moment negatives are permitted.
The rule to carry: a two-pointer window needs a quantity that moves in one direction as the window grows. Sums of positives qualify. Sums of arbitrary integers do not.
The exact-sum variant
“Sum equals target” is a different problem again, and the window does not solve it either, since
shrinking a window whose sum overshoots can skip past an exact match. For an exact target the tool
is a prefix-sum hash map: store each prefix sum with its index and look up prefix[i] - target.
That is O(n) time and O(n) space, and unlike the window it tolerates negatives.
Related problems that use the same shape
The same structure solves a family of questions, and recognising it saves rederiving the loop:
- Longest substring without repeating characters, where the shrink condition is a duplicate rather than a sum.
- Longest substring with at most K distinct characters, where the window carries a frequency map.
- Maximum sum subarray of fixed size K, where the window never changes length and both pointers move together.
- Fruit into baskets, which is the K-distinct problem with K fixed at 2.
The differences are all in the shrink condition. Once that is written down, the surrounding loop is identical every time.
Frequently asked questions
Why is the inner loop a while and not an if?
Because several shorter windows ending at the same
right can all be valid, and only the shortest matters. An if stops at the first.
What should the function return when no subarray reaches the target?
0 by the usual statement of
the problem. That is why best starts at a sentinel rather than 0.
Is the complexity really O(n) with nested loops?
Yes. The inner loop advances left, which moves
at most n times across the whole run, so total pointer movement is bounded by 2n.
Does this work with zeros in the array?
Yes. A zero neither increases nor decreases the sum, so monotonicity still holds in the non-strict sense the proof needs.
Does it work with negative numbers?
No. Use prefix sums with a monotonic deque instead.
What changes for “sum exactly equals target”?
Use a prefix-sum hash map. The window can overshoot and skip the exact match.
Can this be done with binary search?
Yes, in O(n log n), by building prefix sums and binary searching for each start position. The window is strictly better, but the binary search version generalises to some variants more easily.
Why record the length before shrinking?
Because at that instant the window is the smallest valid
one ending at the current right. After shrinking it is no longer valid.
What is the space complexity?
O(1). Three integers, regardless of input size.
How do I recognise a sliding window problem?
Contiguous subarray or substring, a condition that moves in one direction as the window grows, and a question asking for the shortest or longest such range.