Python 3.11+
The examples use the standard Python syntax and containers supported by the browser Judge; the Monotonic Queue invariant is independent of a minor Python release.
Verify in Python docs(opens in a new tab)Pattern1 Practice1 Interview
Monotonic Queue
Maintain a deque ordered by value to query window extrema while elements enter and leave. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.
Recognize it when
Consider Monotonic Queue when the prompt's constraints and required operations match this shape: Maintain a deque ordered by value to query window extrema while elements enter and leave.
On this page · Keep the Best Candidate at the Front
Checking your account…
Sign in to save your code and progress across devices. The lesson and problem statement remain public.
Monotonic Queue Code Labs
Keep the Best Candidate at the Front
A monotonic deque stores live candidate indexes in decreasing value order. The front is always the maximum for the current window.
Expire Indexes Outside the Window
Before reading an answer, remove front indexes at or before index minus width. Values alone cannot reveal expiration, which is why the deque stores indexes.
Trace Monotonic Deque State
Reference
from collections import deque
def max_deque_trace(values,width):
candidates=deque(); trace=[]
for index,value in enumerate(values):
while candidates and candidates[0]<=index-width: candidates.popleft()
while candidates and values[candidates[-1]]<=value: candidates.pop()
candidates.append(index); trace.append(list(candidates))
return tracePractice
Implement max_deque_trace(values,width). Return deque index contents after processing each index for sliding maximum.
Public tests
- Expire and remove dominated indexes
Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor
Remove Dominated Candidates
Before appending a new index, pop back candidates no greater than its value. The new value is both stronger and lives longer, so dominated indexes can never become a future maximum.
Compute Sliding Window Maximums
Reference
from collections import deque
def window_maximums(values,width):
candidates=deque(); result=[]
for index,value in enumerate(values):
while candidates and candidates[0]<=index-width: candidates.popleft()
while candidates and values[candidates[-1]]<=value: candidates.pop()
candidates.append(index)
if index>=width-1: result.append(values[candidates[0]])
return resultPractice
Implement window_maximums(values,width). Return the maximum for every complete fixed-width window.
Public tests
- Read the strongest live front
Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor
Choose a Monotonic Queue or Heap
Use a monotonic queue for extrema over a moving contiguous window in O(n). A heap is more general but needs lazy deletion and O(n log n) or O(n log width). Each deque index enters and leaves at most once.
Explain It in an Interview
Say: “The front is the strongest live index. I expire old fronts, remove weaker backs, append the new index, then read the front.” State how equal values are owned and when a complete window begins.
Python Version Note
Complexity & Invariants
Interview bounds depend on the stated representation, input model, and real Python operations.
| Operation | Average | Worst | Interview note |
|---|---|---|---|
| Monotonic Queue decision loop | O(n) | O(n) | Maintain a deque of in-window indexes whose values decrease from front to back. |
Space
O(k) for the focused Maintain Sliding-Window Maximums implementation.
Assumptions
- Expired indexes are removed before output. Every dominated suffix is removed because the newer value is at least as large and lasts longer; therefore the front is always the current window maximum.
- The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.
Invariants Worth Saying Aloud
- State the precise Monotonic Queue invariant before coding and preserve it after every update, traversal step, or recursive return.
- Indexes increase from front to back.
- Values follow the chosen monotone order and the front is the current optimum.
- Expire indexes that leave the window. Preserve this property after every transition.
- Remove dominated candidates while preserving decreasing values. Preserve this property after every transition.
When To Use Or Avoid Monotonic Queue
Use It When
- Use Monotonic Queue when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
- Use it when indexes increase from front to back.
Choose Another Tool When
- Avoid Monotonic Queue when its decision rule cannot eliminate work or preserve the required state.
- Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.
Common Pitfalls
These are the mistakes most likely to survive a happy-path example and fail a boundary case.
Moving state without a proof
Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.
Prevent it: Write the decision rule beside the loop and verify it against Maintain Sliding-Window Maximums before optimizing.
Avoid
def window_maximums(values, window_size):
passUse instead
from collections import deque
def window_maximums(values, window_size):
candidates = deque()
results = []
for index, value in enumerate(values):
while candidates and candidates[0] <= index - window_size:
candidates.popleft()
while candidates and values[candidates[-1]] <= value:
candidates.pop()
candidates.append(index)
if index >= window_size - 1:
results.append(values[candidates[0]])
return resultsWhere you will hit this: Maintain Sliding-Window Maximums(opens in a new tab)
Breaking the maintained state
Never expires old indexes, so a past maximum leaks into later windows.
Prevent it: Use the public tests and preserve this state: Indexes increase from front to back.
Avoid
from collections import deque
def window_maximums(values, window_size):
q=deque(); out=[]
for i,v in enumerate(values):
while q and values[q[-1]]<=v: q.pop()
q.append(i)
if i>=window_size-1: out.append(values[q[0]])
return outUse instead
from collections import deque
def window_maximums(values, window_size):
candidates = deque()
results = []
for index, value in enumerate(values):
while candidates and candidates[0] <= index - window_size:
candidates.popleft()
while candidates and values[candidates[-1]] <= value:
candidates.pop()
candidates.append(index)
if index >= window_size - 1:
results.append(values[candidates[0]])
return resultsWhere you will hit this: Maintain Sliding-Window Maximums(opens in a new tab)
Hiding Python work in the hot path
Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.
Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(n).
Avoid
from collections import deque
def window_maximums(values, window_size):
q=deque(); out=[]
for i,v in enumerate(values):
while q and values[q[-1]]<=v: q.pop()
q.append(i)
if i>=window_size-1: out.append(values[q[0]])
return outUse instead
from collections import deque
def window_maximums(values, window_size):
candidates = deque()
results = []
for index, value in enumerate(values):
while candidates and candidates[0] <= index - window_size:
candidates.popleft()
while candidates and values[candidates[-1]] <= value:
candidates.pop()
candidates.append(index)
if index >= window_size - 1:
results.append(values[candidates[0]])
return resultsWhere you will hit this: Longest Continuous Subarray Within Limit(opens in a new tab)
Reviewed References
Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.
- Python collections.deque(opens in a new tab)
python-docs · checked 2026-07-12