DSA & Algorithms
Part 8 of 21 · DSA Interview PatternsQueue, Deque & Monotonic Queue — Sliding Extrema & BFS Helpers
Deque and monotonic queue for sliding-window maxima and BFS-friendly fronts.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
You need the max or min of every window of length k
Prefer
A monotonic deque
The front is the current extreme. Worse values behind a new champion can never win, so they leave from the back.
- Each index is pushed and popped at most once.
- The front index is dropped when it is left of i - k.
- Duplicates need an explicit strict or non-strict compare.
Alternative
A fresh heap per window
A heap can do it, with lazy deletes and a worse constant.
- Forgetting to pop the front when it leaves the window.
- Using list.shift in a hot loop and calling it O(1).
- Confusing next-greater (stack) with window-max (deque).
Clean the back, then the front
New index comes in from the back. Expired index leaves from the front.
- 1
Pop worse values from the back
They are older and smaller than the new value. - 2
Push the new index
It might be the max of a later window. - 3
Drop a front that left the window
The front that remains is the answer.
Overview
Deque and monotonic queue for sliding-window maxima and BFS-friendly fronts.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use a queue for FIFO (BFS), a deque for both ends, and a monotonic deque for sliding-window extrema in O(n).
Recognition cues
- sliding window maximum/minimum
- first non-repeating character in a stream
- BFS level order helpers
- constrained subsequence DP with mono deque
Mental model
Flow
- 1
1. See index i
- next2. Pop worse from the back
- 2
2. Pop worse from the back
- next3. Push i
- 3
3. Push i
- next4. Drop front outside the window
- 4
4. Drop front outside the window
- next5. Front is the extreme
- 5
5. Front is the extreme
Lesson map
Queue, Deque & Monotonic Queue — Sliding Extrema & BFS Helpers
Deque and monotonic queue for sliding-window maxima and BFS-friendly fronts.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB in["1. See index i"] back["2. Pop worse from the back"] push["3. Push i"] front["4. Drop front outside the window"] in -->|1. See index i to 2. Pop worse from the back| back back -->|2. Pop worse from the back| push push -->|3. Push i to 4. Drop front outside the window| front
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Sliding max: O(n) time (each index once), O(k) deque space.
- Naive heap-per-window is slower to clean.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Sliding Window Maximum
- Moving Average from Data Stream
- Design Circular Queue
- Shortest Subarray with Sum at Least K
- Jump Game VI
- Constrained Subsequence Sum
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Why deque not heap for window max?
Answer
Deque gives O(1) current max and O(n) total; heap needs lazy deletes.
Invariant?
Answer
Front is best in window; back is newest candidate.
BFS uses queue how?
Answer
FIFO processes nodes by distance/level.
When mono deque in DP?
Answer
When transition is max over a sliding index range.
Moving average?
Answer
Simple queue + running sum - not mono.
Evict rule?
Answer
If dq.front <= i - k, popfront.