Grow, then shrink
A window that stretches on the right and tightens on the left. About 10 minutes.
A window that stretches and shrinks
You're saving up for a phone and want the shortest run of consecutive days whose earnings add up to at least the price. The window no longer has a fixed size.
Keep a left end and a right end. Move the right end forward one day at a time, adding each day in. As soon as the total reaches the target, you've found a candidate. Note its length.
Grow to 2 + 3 + 1 + 2 = 8 ≥ 7. Length 4.
Then squeeze from the left
Once the window is big enough, try to make it shorter. Drop the leftmost day and check again. Keep squeezing, noting each length, until the total falls below the target. Then go back to growing.
This only works because every number is positive: dropping a day can only lower the total. With negative numbers, dropping one could raise it, and the logic breaks.
left = total = 0
best = float("inf")
for right, x in enumerate(nums):
total += x
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float("inf") else bestThe target is 10. The window holds 4, 3, 5, a total of 12. What happens next?
- ANote length 3, then drop the 4
- BAdd the next number
- CDrop the 5
Show the answer
Note length 3, then drop the 4. It's big enough, so note it, then try shorter by dropping from the left.
Shortest window reaching a sum
You get a list of positive whole numbers and a target. Return the length of the shortest run of consecutive numbers whose sum is at least the target, or 0 if there is none.
nums = [2, 3, 1, 2, 4, 3], target = 7 → 2
0 ≤ n ≤ 1,000,000 · 1 ≤ each value ≤ 10^6 · 1 ≤ target ≤ 10^9