What is the Monotonic Queue Technique?
Learn the monotonic queue technique for O(n) sliding window max/min and how to answer this interview question with a clear example.
Expected Interview Answer
A monotonic queue is a deque that keeps its elements in strictly increasing or decreasing order by evicting from the back any element that can never again be the answer, which lets sliding-window maximum/minimum queries run in O(n) total instead of O(n*k).
The deque stores indices, not values, and maintains the invariant that the values at those indices are monotonic from front to back. When a new element arrives, you pop from the back while it would violate the ordering, since any smaller (or larger) element behind a bigger one still in the window can never win once the bigger one is also in range. You also pop from the front whenever the front index falls outside the current window. Because each index is pushed and popped at most once, the whole scan across n elements is amortized O(n), which is why this beats a naive per-window scan or even a heap-based approach that would cost O(n log k).
- O(n) amortized for sliding window max/min
- Beats heap-based O(n log k) approaches
- Stores indices so window eviction is O(1)
- Generalizes to shortest subarray with sum constraints
AI Mentor Explanation
Think of a bowler tracking the fastest delivery within the last six balls using a lineup instead of rechecking all six every time. Whenever a new delivery speed comes in, they discard from the back of the lineup every earlier speed that was slower than the new one, since a slower ball sitting behind a faster ball can never again be the fastest while the faster one is still in the window. The front of the lineup is dropped once that ball is older than six deliveries ago. This way the fastest ball in the current six is always the front entry, found without rescanning the whole over.
Step-by-Step Explanation
Step 1
Store indices in a deque
Keep indices, not values, so the current window bound can be checked against the front index.
Step 2
Pop from the back while violated
Before pushing a new index, remove back indices whose values cannot beat the new value.
Step 3
Pop from the front when out of window
If the front index falls outside the current window (index - k), remove it.
Step 4
Front is always the answer
After each push/evict, the deque front holds the max (or min) for the current window in O(1).
What Interviewer Expects
- Explain why the deque stores indices rather than values
- Justify the eviction rule with an amortized O(n) argument
- Distinguish this from a heap-based O(n log k) solution
- Apply it correctly to sliding window maximum
Common Mistakes
- Storing values instead of indices, losing the ability to check window bounds
- Forgetting to evict expired indices from the front
- Popping the wrong end of the deque during eviction
- Claiming O(n log n) instead of the true amortized O(n)
Best Answer (HR Friendly)
“A monotonic queue is a way to track the max or min in a sliding window without rechecking every element each time. I keep a list that only holds candidates that could still win, throwing away anything that is now guaranteed to lose, which keeps the whole scan linear instead of quadratic.”
Code Example
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, values decreasing
result = []
for i, num in enumerate(nums):
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return resultFollow-up Questions
- How would you adapt this for sliding window minimum instead?
- Why is this faster than using a heap with lazy deletion?
- How would you find the shortest subarray with sum at least a target using a monotonic deque?
- What breaks if you store values in the deque instead of indices?
MCQ Practice
1. What does a monotonic queue for sliding window maximum store in its deque?
Storing indices lets the algorithm check whether the front index has fallen outside the current window.
2. What is the amortized time complexity of processing all n elements with a monotonic queue?
Each index is pushed and popped at most once across the whole scan, giving amortized O(n) total.
3. When is an index evicted from the front of the deque?
The front index is removed once it is older than the window allows (index <= current index - k).
Flash Cards
What does a monotonic queue store for sliding window max? — Indices into the array, kept in decreasing order of their values.
Why is the back of the deque evicted on a new larger value? — Because smaller values behind a larger one can never be the max again while it remains in range.
What is the total time complexity across n elements? — Amortized O(n), since each index is pushed and popped at most once.
How does this compare to a heap-based approach? — It beats a heap with lazy deletion, which costs O(n log k) instead of O(n).