Shortest subarray with a sum at least the target
Given an array nums of positive integers and an integer
target, return the length of the shortest contiguous subarray whose sum is at least
target. If no such subarray exists, return 0.
Examples
| Input | Output | Why |
|---|---|---|
nums = [2, 3, 1, 2, 4, 3], target = 7 | 2 | The subarray [4, 3] sums to 7 and nothing shorter reaches it. |
nums = [1, 1, 1, 1, 1, 1, 1, 1], target = 11 | 0 | The whole array sums to 8. |
nums = [1, 4, 4], target = 4 | 1 | A single element is enough. |
Constraints
- 1 ≤ n ≤ 10⁵
- 1 ≤ nums[i] ≤ 10⁴
- 1 ≤ target ≤ 10⁹
- Every value is strictly positive
Hints
Hint 1
There are n(n+1)/2 subarrays. Enumerating them is O(n²) even with a running sum. What property of the input lets you skip most of them?
Hint 2
Every value is positive, so extending a window can only increase its sum and shrinking it can only decrease it. The sum is monotone in the window.
Hint 3
Grow the right end until the window qualifies. Then, before growing again, shrink from the left for as long as it still qualifies — each shrink gives a shorter candidate.
Dry run on [2,3,1,2,4,3],7
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 12nums20lo/hi3112234435sum2target7best—
Add nums[0] = 2. The window is [0, 0] and sums to 2, still short of 7.
-
Step 2 / 12nums20lo31hi12234435sum5target7best—
Add nums[1] = 3. The window is [0, 1] and sums to 5, still short of 7.
-
Step 3 / 12nums20lo3112hi234435sum6target7best—
Add nums[2] = 1. The window is [0, 2] and sums to 6, still short of 7.
-
Step 4 / 12nums20lo311223hi4435sum8target7best—
Add nums[3] = 2. The window is [0, 3] and sums to 8, which reaches the target.
-
Step 5 / 12nums20lo311223hi4435sum8target7best4
Sum 8 ≥ 7, so length 4 is a candidate. Drop nums[0] = 2 and see whether it still qualifies.
-
Step 6 / 12nums2031lo122344hi35sum10target7best4
Add nums[4] = 4. The window is [1, 4] and sums to 10, which reaches the target.
-
Step 7 / 12nums2031lo122344hi35sum10target7best4
Sum 10 ≥ 7, so length 4 is a candidate. Drop nums[1] = 3 and see whether it still qualifies.
-
Step 8 / 12nums203112lo2344hi35sum7target7best3
Sum 7 ≥ 7, so length 3 is a candidate. Drop nums[2] = 1 and see whether it still qualifies.
-
Step 9 / 12nums20311223lo4435hisum9target7best3
Add nums[5] = 3. The window is [3, 5] and sums to 9, which reaches the target.
-
Step 10 / 12nums20311223lo4435hisum9target7best3
Sum 9 ≥ 7, so length 3 is a candidate. Drop nums[3] = 2 and see whether it still qualifies.
-
Step 11 / 12nums2031122344lo35hisum7target7best2
Sum 7 ≥ 7, so length 2 is a candidate. Drop nums[4] = 4 and see whether it still qualifies.
-
Step 12 / 12nums203112234435answer2
Nothing shorter than 2 ever qualified. Return 2.
How to think about it
The constraint that carries this problem is all values are positive. It means the window sum moves in one direction as each end moves, so you never have to reconsider a position you have passed.
Keep a window [lo, hi] and a running sum. Move hi right one step at a
time, adding as you go. The moment the sum reaches the target, the window is a valid answer — but
probably not the shortest one ending at hi. So shrink: while the sum is still at least
the target, record the length and move lo right, subtracting as you go.
Each index enters the window once and leaves it once, so the two pointers together take 2n steps. The work is O(n) even though the inner loop is nested inside the outer one, which is the part worth saying out loud in an interview.
Drop the positivity and this breaks: a negative value can make a longer window sum less than a shorter one, so a passed index may still matter. That version needs a monotonic deque over prefix sums, and it is a genuinely harder problem.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def shortest_subarray(nums, target):
n = len(nums)
best, lo, total = n + 1, 0, 0
for hi, value in enumerate(nums):
total += value
while total >= target: # shrink while it still qualifies
best = min(best, hi - lo + 1)
total -= nums[lo]
lo += 1
return 0 if best == n + 1 else best#include <vector>
#include <algorithm>
int solve(const std::vector<int>& nums, long long target) {
const int n = static_cast<int>(nums.size());
int best = n + 1, lo = 0;
long long total = 0; // 64-bit: the sum can reach 10^9
for (int hi = 0; hi < n; ++hi) {
total += nums[hi];
while (total >= target) { // shrink while it still qualifies
best = std::min(best, hi - lo + 1);
total -= nums[lo];
++lo;
}
}
return best == n + 1 ? 0 : best;
}class Solution {
public int shortestSubarray(int[] nums, long target) {
int n = nums.length, best = n + 1, lo = 0;
long total = 0; // 64-bit: the sum can reach 10^9
for (int hi = 0; hi < n; hi++) {
total += nums[hi];
while (total >= target) { // shrink while it still qualifies
best = Math.min(best, hi - lo + 1);
total -= nums[lo];
lo++;
}
}
return best == n + 1 ? 0 : best;
}
}function shortestSubarray(nums, target) {
const n = nums.length;
let best = n + 1, lo = 0, total = 0;
for (let hi = 0; hi < n; hi++) {
total += nums[hi];
while (total >= target) { // shrink while it still qualifies
best = Math.min(best, hi - lo + 1);
total -= nums[lo];
lo++;
}
}
return best === n + 1 ? 0 : best;
}fn solve(nums: &[i64], target: i64) -> usize {
let n = nums.len();
let (mut best, mut lo, mut total) = (n + 1, 0usize, 0i64);
for hi in 0..n {
total += nums[hi];
while total >= target { // shrink while it still qualifies
best = best.min(hi - lo + 1);
total -= nums[lo];
lo += 1;
}
}
if best == n + 1 { 0 } else { best }
}import Data.Array
-- An array rather than a list, so that dropping from the left stays O(1) and the
-- whole scan stays linear. go carries: right end, left end, running sum, best so far.
solve :: [Int] -> Int -> Int
solve nums target
| best > n = 0
| otherwise = best
where
n = length nums
arr = listArray (0, n - 1) nums
best = go 0 0 0 (n + 1)
go hi lo total acc
| hi >= n = acc
| otherwise = let (lo', total', acc') = shrink lo (total + arr ! hi) acc
in go (hi + 1) lo' total' acc'
where
shrink l t a -- shrink while it still qualifies
| t >= target = shrink (l + 1) (t - arr ! l) (min a (hi - l + 1))
| otherwise = (l, t, a)Where people lose marks
- Returning the running best as 0 when nothing qualifies, but initialising best to 0 as well — then a real answer of, say, 3 never replaces it. Initialise to n + 1 or to infinity and convert at the end.
- Shrinking with
while (sum > target)rather than>=, which stops one step early and returns a length one too long. - Summing into a 32-bit integer. With n = 10⁵ and values up to 10⁴ the total reaches 10⁹, which is close enough to the limit to be worth a 64-bit accumulator.
- Reaching for prefix sums and binary search, O(n log n). It is a correct answer to a question that has an O(n) one.
Variants to try
- What if the values can be negative? (Prefix sums plus a monotonic deque, still O(n), but the argument is much harder.)
- Return the subarray itself rather than its length: keep the lo index alongside the best length.
- Shortest subarray with sum exactly the target: the monotone argument fails, and a hash map of prefix sums replaces it.
- Longest subarray with sum at most the target: the same window, with the comparison reversed.
Next problems
Write a solution and run it against the real test table.
Keep going
Longest run of distinct characters
The window that grows on the right and shrinks on the left, and the invariant that makes it correct.
Open the problem → Sliding windowThe pattern behind it
A window that grows on the right, shrinks on the left, and holds an invariant at all times.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.