Variable sliding window
Grow the window one item at a time. As soon as it breaks the rule, here a sum over the limit, shrink it from the left until it fits again. The window only ever moves forward, so the whole scan is linear.
3127421152
Find the longest run of items whose sum is at most 8. Press play or step forward to start.
1function longestWithin(a, limit) {2 let lo = 0, sum = 0, best = 0;3 for (let hi = 0; hi < a.length; hi++) {4 sum += a[hi];5 while (limit < sum) {6 sum -= a[lo];7 lo++;8 }9 if (best < hi - lo + 1) best = hi - lo + 1;10 }11 return best;12}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | everything fits: lo never moves |
| average | n | any limit |
| worst | n | each item joins once and leaves at most once |
| space | 1 | two indexes and a running sum |
Where it breaks
- Negative values. Shrinking only helps if dropping an item lowers the sum. With negatives, dropping one can raise it, and the window can skip the right answer. Prefix sums handle that case.
- "There is a nested loop, so it must be n²." The inner
whileonly ever moves lo forward, and lo never passes the end. Across the whole run it moves at most n times, so the total is still linear. - Using
ifinstead ofwhile. One item joining can push the sum far over the limit. Pick Limit 8 and watch 7 join: lo has to move three times before the window fits again.