Home▸Algorithms & AI▸Sliding Window Minimum via Monotonic Deque

🪟 Sliding Window Minimum via Monotonic Deque

Explore how a monotonic deque tracks the minimum (or maximum) of the last K elements in a data stream in amortized constant time, with an interactive simulator showing pushes, pops, and window slides in real time.

Algorithms & AI3DModerate60 FPS

The simulator streams a sequence of numeric values one at a time into a sliding window of size K, visually showing the deque as it grows and shrinks: back-pops removing dominated values before each push, front-pops trimming expired indices, and the current window minimum highlighted at the front of the deque after every step.

🔬 What It Demonstrates

🎮 How to Use

Set the window size K and either enter a custom sequence or generate a random stream, then press step to advance one element at a time or play to animate the full stream automatically. Watch the deque panel update live, noting which values get popped from the back (because a smaller newcomer displaced them) versus popped from the front (because they aged out of the window), and observe the running minimum displayed alongside the naive brute-force minimum for comparison.

💡 Did You Know?

Even though popping from the back can remove several elements in a single step, no element is ever pushed or popped more than once in its lifetime across the entire stream, which is exactly why the total work stays linear in the number of elements despite individual steps looking expensive.

⚙ Under the hood

algorithmsdata-structuresdequesliding-windowmonotonic-queueamortized-analysiscomputer-sciencestreaming-data

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install