Sliding Window
Keep a contiguous range and update its summary as it moves, instead of rescanning it.
Decision · step 2 of 7Sliding Window: Largest sum of 3 in a row
2 leaves and 1 enters, so the sum is 7. The best stays at 8.
What you will see
A physical frame slides over the row; one value enters and one leaves per step.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Cells announce index, value and whether they are inside the window; each step announces the window bounds and the running value.
Reduced motion: The window frame snaps to its new bounds with a crossfade.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Sliding Window covers these too, in the same run.