Sliding Window Minimum via Monotonic Deque

How the Monotonic Deque Works

The core idea is to maintain a deque of indices (not just values) from the data stream, kept in an order where the corresponding values are monotonically increasing from front to back when tracking a minimum. Each time a new element arrives, two operations happen in sequence.First, the algorithm looks at the back of the deque and repeatedly pops elements whose value is greater than or equal to the new element. This step is the heart of the technique: if the new element is smaller than something already stored, that older, larger element can never again be reported as the window minimum while the new element remains inside the window, because the new element is both smaller and more recent, so it will still be valid after the old one has expired. There is simply no future scenario where the discarded element would be useful, so removing it is safe.Second, the new element's index is pushed onto the back of the deque. At this point the deque is again fully monotonic: increasing from front to back.Third, before reading the minimum, the algorithm checks the front of the deque. If the index stored there has fallen outside the current window (its position is more than K steps behind the newest element), it is popped from the front, because it is no longer part of the window even though its value might still be small.After these steps, the value at the front index is guaranteed to be the minimum of the current window. It survived every comparison against smaller newcomers, and it has not yet aged out of range, so nothing else in the deque can beat it.

Why It Is Amortized Constant Time

At first glance, popping from the back "while" a condition holds looks like it could run for a long time on a single step, making the algorithm seem like it might occasionally cost O(K) work. The nested-looking loop, an outer loop over the stream and an inner loop over pops, appears to threaten the constant-time promise. The resolution lies in amortized analysis, which studies total cost across a whole sequence of operations rather than the worst case of any single one.The key observation is that every index is pushed onto the deque exactly once, when it first arrives from the stream. From that point forward, an index can only ever be removed twice in its entire lifetime: once from the back, if a later smaller element causes it to be popped, or once from the front, if it ages out of the window, but never both, since once it is popped it is gone. Across an entire stream of n elements, there are at most n pushes and at most n pops in total, no matter how the pops are distributed across individual steps.Some steps may see several back-pops happen in a row, appearing expensive, but those pops are "paid for" by pushes that happened earlier and have not yet been charged against any removal. Summing the total work, pushes plus pops, over the whole stream gives at most 2n operations, so the average cost per stream element is O(1), even though any individual step's cost can vary. This is the essence of amortized O(1) per step: not that every single step is cheap, but that the total cost divided by the number of steps is bounded by a constant.

Maximum Instead of Minimum

The same technique flips cleanly to track a window maximum instead of a minimum. The only change needed is the comparison direction: instead of popping back elements that are greater than or equal to the newcomer, the algorithm pops back elements that are less than or equal to it, keeping the deque monotonically decreasing from front to back. The reasoning is symmetric: a smaller, older element can never again be the maximum once a larger, more recent element has joined the window, so it is safe to discard.Everything else stays identical. Indices are still pushed at the back after clearing dominated entries, the front is still trimmed whenever it falls outside the window, and the front of the deque still gives the answer in constant time. Some implementations even track both a minimum-deque and a maximum-deque simultaneously over the same stream, which is useful for computing the range (max minus min) of every window, a common requirement in signal processing and anomaly detection.It is worth noting what the deque does not store: it does not store every value in the window, only the subsequence of values that could plausibly become the answer at some future point. In the worst case (a strictly monotonic stream) the deque can hold up to K entries, but in the best case, such as a stream that keeps decreasing, it can hold as few as one entry. This adaptive size is why the technique outperforms a naive full rescan, which always inspects all K elements regardless of their relative order.

Comparing to Alternative Approaches

Before the monotonic deque became a standard tool, sliding window minimum problems were typically solved with less efficient structures. A naive scan recomputes the minimum over all K elements every time the window moves, giving O(n·K) total time, which becomes painfully slow for large windows or long streams.A balanced binary search tree or a heap with lazy deletion can also track the window minimum, supporting insertions and removals in O(log K) time each. This is correct and reasonably fast, and it generalizes to problems where you need the k-th smallest value rather than just the minimum, but it carries a logarithmic factor and higher constant overhead compared to the deque approach, along with the complexity of handling stale entries that have aged out of the window.The monotonic deque achieves the same result with only amortized O(1) per element and a much simpler implementation: a single array or linked list used as a double-ended queue, with no comparisons beyond simple greater-than or less-than checks. Its limitation is that it only answers the minimum or maximum query, not arbitrary rank queries, so if a problem needs the median or the k-th smallest value in a window, a tree or heap-based structure remains necessary. For the specific and very common task of tracking a running minimum or maximum, though, the monotonic deque is the fastest and simplest tool available, which is why it appears so frequently in coding interviews and in production streaming systems alike.

Real-World Applications

The sliding window minimum and maximum pattern shows up across many domains that process continuous or large sequential data. In stock price analysis, traders and algorithms often need the lowest or highest price over a trailing window, such as the last 30 trading days, to compute indicators like Donchian channels or to detect breakouts; recomputing this from scratch on every new tick would be far too slow for high-frequency data, but a monotonic deque updates it instantly as each new price arrives.In real-time monitoring dashboards, systems tracking metrics like server latency, temperature sensors, or network throughput frequently display a rolling minimum or maximum over the last N samples to flag anomalies or highlight recent extremes. Because these dashboards ingest a continuous stream of readings, an amortized O(1) update per sample keeps the system responsive even under heavy data rates, where a naive rescanning approach could fall behind.In convolution and pooling operations used in image processing and convolutional neural networks, a max-pooling layer computes the maximum value within a sliding window over an image or feature map, often moving that window across two dimensions. While a full two-dimensional max-pooling implementation extends the idea further, the one-dimensional monotonic deque is the building block: applying it along rows and then along columns lets an implementation compute two-dimensional sliding window maxima efficiently, which matters enormously when processing large images or high-resolution feature maps repeatedly during training.Beyond these examples, the same pattern appears in network packet analysis, genomic sequence scanning, and any scenario where a bounded historical window must be queried repeatedly as new data continuously arrives.

Frequently asked questions

Try it live

Everything above runs in your browser — open Sliding Window Minimum via Monotonic Deque and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.