Shortest subarray with sum at least target
We'll cover the following
Given positive numbers and a target, find the length of the shortest subarray whose sum is at least the target.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
L/R30
91
32
83
24
25
26
37
58
79
110
911
512
613
714
915
Add 3. Sum is 3. Not enough yet, keep growing.
sum 3 · target 18 · best -
1 / 31
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(1) | R grows once per item and L only moves forward. |
In Python
def min_len(target, nums):
l = cur = 0; best = float('inf')
for r, x in enumerate(nums):
cur += x
while cur >= target: # valid: try to shorten
best = min(best, r - l + 1)
cur -= nums[l]; l += 1
return 0 if best == float('inf') else bestSummary: say it in the interview
- This time the window is allowed to shrink while it is already good. Grow R until the sum reaches the target, then pull L in as far as you can and record the length each time.
- Time O(n), space O(1). R grows once per item and L only moves forward.