Algorithms / Monotonic Queue Sliding Window

Least You Need to Know: Monotonic Queues and Sliding-Window Extremes

A monotonic deque keeps the current window's best candidates in order, so the front always holds the maximum or minimum. It is the standard pattern for sliding-window extrema because it supports both expiration from the left and dominance cleanup from the right.

The least you need to know

The deque front stores the best currently valid candidate for the window.
Indices expire from the front when they fall out of the window.
While pushing a new value, dominated worse values are removed from the back.
Indices are safer than raw values because you must know when an item leaves the window.
Each index enters and leaves the deque at most once, so the total work is linear.

Key notation

window [L, R] current contiguous range under consideration

deque front current max or min for the window

dominated can never win while a better later candidate remains valid

Tiny worked example

For sliding-window maximum, maintain deque values in decreasing order.
Before appending a new index, pop smaller values from the back because the new value dominates them.
When the left boundary moves, pop the front if that index expired.
Then the front is the current window maximum.

Common mistakes

Students often keep raw values and then cannot tell which copy expired.
Students often forget to remove expired indices from the front.
Students often recompute each window maximum from scratch instead of maintaining a live candidate deque.

How to recognize this kind of problem

The prompt asks for every window's maximum, minimum, or another rolling extreme.
The window moves one step at a time and old elements expire.
You need both fast insertion of new elements and fast removal of stale ones.