Deque
A deque, a double-ended queue, lets you add and remove at both ends. That fits a sliding window: new items join at the back, items that slide out leave from the front, and values beaten by a newer, bigger one are dropped from the back because they can never be the maximum again.
131275462
Find the largest value in every window of 3 items. Press play or step forward to start.
1function windowMax(a, k) {2 const dq = [], out = [];3 for (let i = 0; i < a.length; i++) {4 while (dq.length > 0 && a[dq.at(-1)] <= a[i]) {5 dq.pop();6 }7 dq.push(i);8 if (dq[0] === i - k) dq.shift();9 if (i >= k - 1) out.push(a[dq[0]]);10 }11 return out;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 | rising input: each item clears the deque |
| average | n | any window size |
| worst | n | checking every window instead costs n · k |
| space | k | at most one window of indexes in the deque |
Where it breaks
- Storing values instead of indexes. To know when the front has slid out of the window, the deque needs positions. Store indexes and look the values up.
- Falling input keeps everything. Pick Falling: each item is smaller than the one before, so nothing is beaten. The deque fills to k items and only the front-removal keeps it short.
- Re-scanning every window. Taking the max of each window separately costs n · k. Here every index joins the deque once and leaves at most once, so the whole run stays linear.