Sliding window
Neighbouring windows share all but two items. So instead of adding up every window from scratch, slide it: add the item that comes in on the right and subtract the one that drops off the left.
4271835629
Find the largest sum of 3 items in a row. Press play or step forward to start.
1function maxWindowSum(a, k) {2 if (k < 1 || k > a.length) return null;3 let sum = 0;4 for (let i = 0; i < k; i++) sum += a[i];5 let best = sum;6 for (let i = k; i < a.length; i++) {7 sum += a[i] - a[i - k];8 if (best < sum) best = sum;9 }10 return best;11}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | every input: each item joins once and leaves once |
| average | n | whatever the window size |
| worst | n | re-summing each window instead costs n · k |
| space | 1 | just the running sum and the best |
Where it breaks
- Re-summing each window. Two nested loops cost about n · k additions. On a million items with a window of a thousand, that is a billion additions against two million.
- Off-by-one at the edges. The item leaving is
a[i - k], nota[i - k + 1]. Get it wrong and the window quietly grows or shrinks by one as it slides. - A window that does not fit. If k is larger than the array there is no window at all. Check it up front instead of reading past the end.