Monotonic-Deque Windows — 3D prototype

LC 239 · Sliding Window Maximum · ◐ Light

Sliding Window Maximum — deque of candidate indices

WebGL isn't available here, so the 3D view is turned off. The step-by-step walkthrough below says the same thing.

0 / 0

front = window max in deque (still a candidate) popped from back — dominated forever popped from front — aged out of the window window slab (k) ghost = value still in the array

What the third axis buys you. Drag to orbit. The ribbons receding into the back are each index's lifetime in the deque — hit Timeline for the top-down read. There is exactly one ribbon per index, and no ribbon ever restarts: each index enters once and leaves once, which is the whole amortized-O(n) argument as a picture rather than a claim. The descending staircase on the near shelf is the monotonic invariant; watch it kink for a moment when a taller value arrives, then get repaired by the back-pops.

Text fallback (this stays in the page for no-JS / print / reduced-motion):

Window [1, 3, -1]: 3 beats 1, so 1 is dropped → front is 3. Max 3.
[3, -1, -3]: front still 3. Max 3.
[-1, -3, 5]: 5 beats everything before it → front 5. Max 5.
[-3, 5, 3]: front 5. Max 5.
[5, 3, 6]: 6 beats 5 and 3 → front 6. Max 6.
[3, 6, 7]: 7 beats all → front 7. Max 7.