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.
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
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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Monotonic Stacks for Range Boundaries and Histogram Areas.
Least You Need to Know: Monotonic Stacks for Range Boundaries and Histogram AreasRelated lessons
Keep going with nearby lessons in the same topic.