Monotonic Queue (Sliding Window Maximum)

Question 1

In the Sliding Window Maximum problem, how does a Monotonic Queue differ structurally from a Monotonic Stack?

Accepted Answer

The queue uses a deque to support removal from both ends for expiry and pruning — Monotonic Queue uses a deque (double-ended queue) to remove old elements from front when they exit the window.

Question 2

A monotonic queue is typically implemented with a…

Accepted Answer

A deque (double-ended queue) — A deque lets you remove expired elements from the front AND pop dominated elements from the back, both in O(1) — the basis of the monotonic queue.

Question 3

What classic problem does a monotonic queue solve in O(n)?

Accepted Answer

Sliding window maximum in O(n) — It maintains a decreasing deque of candidate maxima so the front is always the current window's maximum — O(n) total versus O(n log n) with a heap.

Question 4

In a DECREASING monotonic deque (for window max), before pushing a new element you…

Accepted Answer

Pop from the back all elements smaller than the new one — Smaller elements at the back can never be the maximum while the larger new element is in the window, so they're discarded — keeping the deque decreasing.

Question 5

How are elements removed when they fall OUT of the sliding window?

Accepted Answer

From the front of the deque (the oldest in-window candidate) — The front holds the candidate extreme; if its index is no longer within [i−k+1, i], pop it from the front. Storing indices makes this check easy.

Question 6

Why is the monotonic queue O(n) overall despite inner loops?

Accepted Answer

Because each element is pushed and popped at most once from the deque — Every element is pushed once and popped at most once (front or back), bounding total deque operations at O(n).

Question 7

Compared to a max-heap for sliding window maximum, the monotonic deque…

Accepted Answer

It achieves O(n) total time by amortizing push and pop operations across elements — A heap can't cheaply remove out-of-window elements (lazy deletion adds overhead); the deque cleanly expires from the front, giving a tighter O(n).

Question 8

For sliding window MINIMUM, the deque is kept…

Accepted Answer

Increasing (smallest at front — the mirror of the max version) — An increasing deque keeps the smallest candidate at the front; pop larger elements from the back before pushing — the mirror of the max version.

Question 9

What does the FRONT of the deque always represent (window max version)?

Accepted Answer

The maximum value in the current window — By construction the deque is decreasing and front indices are in-window, so the front element is the current window's maximum — readable in O(1).

Question 10

Storing INDICES (not values) in the monotonic deque is important because…

Accepted Answer

You can directly compare indices to determine window membership — You need each candidate's position to know when it leaves the window (index < i−k+1). The value is fetched via the index when reporting the answer.

Monotonic Queue (Sliding Window Maximum)

Which end does it leave from?

Test your knowledge

In the Sliding Window Maximum problem, how does a Monotonic Queue differ structurally from a Monotonic Stack?

The short version

In more depth

Deque Magic

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?