Stack/QueueData structureaka monotonic deque, sliding window deque

Monotonic Queue

A deque kept in sorted order so the max (or min) of a sliding window is always at the front.

▶ Visualize Pattern: Sliding Window Practice (1)

Progress

Definition

A monotonic queue is a Deque of indices that stays sorted by value. For a window maximum it is kept decreasing: before pushing i at the back, pop every index whose value is ≤ a[i]. The front is then always the index of the maximum in the current window.

When the window slides, the index that fell out of the window is removed from the front only if it is still at the front — smaller elements that were already dominated were discarded at push time.

This yields the sliding window maximum in O(n) total, versus O(n log n) with a heap or O(nk) naively. The same structure with a prefix-sum array solves "shortest subarray with sum at least K".

dequesliding windowO(n)window maximumamortized

Intuition

A mental model before the formal terms.

A queue at a nightclub where a bouncer only keeps people who could still be "the tallest person in the room" at some future moment. When a tall person arrives, everyone shorter in line can never be the tallest again while the tall one is present, so they are sent home immediately. The line is therefore sorted tallest-first, and the tallest currently inside is always at the front. When the person at the front leaves because their time is up, the next tallest is right behind.

How it works

Maintain a deque dq of indices. Invariant: a[dq[0]] ≥ a[dq[1]] ≥ … (for max).
For each new index i: while dq is non-empty and a[dq.back] <= a[i], popBack(). Then pushBack(i).
Slide: while dq.front <= i - k, popFront() — that index is outside the window.
Once i >= k - 1, a[dq.front] is the maximum of window [i-k+1, i].
For a minimum, flip the comparison to >=.

Why it works

An index j removed from the back by i has a[j] ≤ a[i] and j < i, so i stays in every future window that contains j and is at least as large — j can never be the answer again.

Indices surviving in the deque are in increasing index order and decreasing value order, so the front is both inside the window (after expiring old indices) and the largest.

Each index is pushed once and popped at most once (from either end), giving O(n) total.

Operations

Operation	Description	Cost
push(i)	Pop dominated indices from the back, then append i.	O(1) amortized
expire(i, k)	Pop the front while it is outside the window ending at i.	O(1) amortized
max() / min()	Value at the front index.	O(1)

Recognition

How to tell a problem wants this.

A fixed-size window slides over an array and each step asks for the max or min of the window.
A DP transition of the form dp[i] = a[i] + max(dp[j]) for j in [i-k, i-1] — the monotonic queue optimises it from O(nk) to O(n).
"Shortest subarray with sum ≥ K" with negative numbers (monotonic queue over prefix sums).
Constraints n ≤ 10^5 and k up to n rule out the naive O(nk).

“contiguous subarray” → Sliding Window “next greater element” → Monotonic Stack

Interactive demo

Play, step, change the input. ← → and space work too.

Array | k — Numbers, then a pipe, then window size k — e.g. "1, 3, -1, -3, 5, 3, 6, 7 | 3"

-1

-3

deque (front → back, idx:val)

window maxima

1/23Maximum of every window of size k=3. A deque keeps candidate indices with decreasing values: the front is always the current maximum, and anything smaller than a newer element can never be a maximum again.

Current windowEntering elementIn dequeWindow maximumEvicted

PseudocodeLearn Monotonic Queue →

1dq = deque()  # indices, values decreasing front→back
2for i in 0 .. n-1:
3  while dq and a[dq.back] <= a[i]: dq.pop_back()
4  dq.push_back(i)
5  if dq.front <= i - k: dq.pop_front()
6  if i >= k-1: out.append(a[dq.front])

Variables

Complexity

access O(1)

search O(k)

insert O(1) amortized

delete O(1)

Speed

Pseudocode

1windowMax(a, k):
2  dq = deque(); out = []
3  for i in 0..n-1:
4    while dq and a[dq.back] <= a[i]: dq.popBack()
5    dq.pushBack(i)
6    if dq.front <= i - k: dq.popFront()
7    if i >= k - 1: out.append(a[dq.front])
8  return out

Implementation

1from collections import deque
2 
3 
4class MonotonicQueue:
5    """A deque of indices kept strictly decreasing by value, so the front is
6    always the maximum of the current window."""
7 
81 · State: the values and a decreasing deque of indices (front = max)
9    def __init__(self, values: list[int]) -> None:
10        self.values = values
11        self.dq: deque[int] = deque()
12 
132 · push: drop every index this value dominates, then append
14    def push(self, i: int) -> None:
15        while self.dq and self.values[self.dq[-1]] <= self.values[i]:
16            self.dq.pop()
17        self.dq.append(i)
18 
193 · pop_expired: drop the front once it slides out of the window
20    def pop_expired(self, window_start: int) -> None:
21        if self.dq and self.dq[0] < window_start:
22            self.dq.popleft()
23 
244 · max: the front index always holds the window maximum
25    def max(self) -> int:
26        return self.values[self.dq[0]]
27 
28 
295 · One pass over the array: every index enters and leaves the deque once
30def sliding_window_max(nums: list[int], k: int) -> list[int]:
31    if k <= 0 or len(nums) < k:
32        return []
33    q = MonotonicQueue(nums)
34    out: list[int] = []
35    for i, _ in enumerate(nums):
36        q.push(i)
37        q.pop_expired(i - k + 1)
38        if i >= k - 1:
39            out.append(q.max())
40    return out

Walkthrough

collections.deque is the real thing: append, pop, appendleft and popleft are all O(1), so no head-cursor trick is needed.
self.dq[-1] peeks the back and self.dq[0] peeks the front — deque supports O(1) indexing only at the two ends, and O(n) in the middle.
while self.dq and ... short-circuits, which is what keeps self.dq[-1] from raising IndexError.
for i, _ in enumerate(nums) walks indices while making it explicit that the value is unused — the algorithm reads values only through self.values.
The <= comparison drops ties, which is what bounds the deque at k entries and keeps space O(k).

Complexity (this implementation)

time O(n) · space O(k)

Unlike the JavaScript version, popleft actually frees the slot, so the allocation stays O(k) rather than O(n).

Language notes

collections.deque is a doubly linked list of fixed-size blocks — O(1) at both ends, but dq[n // 2] is O(n), so never treat it as a random-access list.
deque(maxlen=k) exists but is the wrong tool here: it silently discards from the far end, whereas this algorithm must choose which end to drop.
The annotation deque[int] requires Python 3.9+; earlier versions need Deque[int] from typing.
For the pure sliding-window-maximum problem, itertools and heapq.nlargest are both tempting and both worse — the heap variant is O(n log k) with lazy deletion.

Common mistakes in this language

Using a list and pop(0) instead of a deque and popleft() — the O(n) front removal makes the sweep O(n·k).
Writing self.dq.pop(0) on a deque, which raises TypeError: deque.pop takes no argument, the front removal is popleft.
Reversing the and in the guard (self.values[self.dq[-1]] <= ... and self.dq), which raises IndexError on the first empty-deque call.

Language differences that matter here

Deque support: Python has collections.deque and C++ has std::deque, both O(1) at either end; JavaScript and TypeScript have none, so the front removal is emulated with a head cursor because Array.prototype.shift() is O(n).
Live space therefore differs: C++ and Python hold O(k) indices, while the JS/TS head-cursor array allocates O(n) and keeps O(k) live.
Peeking the ends: C++ front()/back(), Python dq[0]/dq[-1], JS/TS dq[head]/dq[dq.length - 1] — only Python indexes the back with a negative index.
Empty-container access is undefined behaviour in C++, an IndexError in Python, and a silent undefined in JS/TS, so the non-empty guard is load-bearing in every language for a different reason.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Front (current max/min) only.
Search	O(k)	O(k)
Insert	O(1) amortized	O(k)
Delete	O(1)	O(1)	Expiry from the front.
Update	—	—
Push	O(1) amortized	O(k)
Expire front	O(1)	O(1)
Query max/min	O(1)	O(1)
All n windows	O(n)	O(n)
Space	O(k)

Advantages & disadvantages

Advantages

Sliding window max/min in O(n) total with O(k) extra space.
Strictly better than a heap for fixed windows: no log factor, no lazy deletion.
Generalises to DP optimisation over a bounded lookback.

Disadvantages

Only supports windows that move monotonically forward; random deletions are not possible.
Requires storing indices and careful expiry logic.
Does not support arbitrary range queries — use a Sparse Table or Segment Tree for those.

Use cases

Sliding window maximum / minimum.
Optimising dp[i] = best(dp[i-k..i-1]) + cost transitions (jump game VI, constrained subsequence sum).
Shortest subarray with sum at least K using prefix sums.
Real-time max/min over the last k sensor readings.

Use it when

Max/min over a fixed-size window that slides forward.
DP where each state depends on the best of the previous k states.
Streaming data where old samples expire in arrival order.

Avoid it when

Window elements are removed in non-FIFO order — use a Priority Queue with lazy deletion or a balanced tree.
Queries are arbitrary [l, r] ranges — use a Sparse Table (static) or Segment Tree (dynamic).
You need nearest greater/smaller per element rather than window extremes — that is a Monotonic Stack.

Alternatives

Priority Queue Sparse Table Segment Tree Monotonic Stack

Common mistakes

Expiring the front by value instead of by index; duplicates make value-based expiry wrong.
Using strict < at the back for a max queue; equal values then pile up and the window can hold stale duplicates (still correct but wastes space) — decide deliberately.
Emitting an answer before the first full window (i < k - 1).
Using Array.shift() in JavaScript for popFront, turning the O(n) algorithm into O(n²).

Interview patterns

Sliding Window Maximum (LeetCode 239) — the canonical problem.
Jump Game VI / Constrained Subsequence Sum: dp[i] = a[i] + max(dp[i-k..i-1]).
Shortest Subarray with Sum at Least K: increasing deque over prefix sums, pop front while P[i] - P[front] >= K.
Longest continuous subarray with absolute diff ≤ limit: one max-queue and one min-queue.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Recognizing a sliding-window problemIntermediate
Next greater element and the monotonic stackIntermediate

Mock interviews

Minimum Size Subarray SumIntermediate
Longest Substring Without Repeating CharactersIntermediate
Daily TemperaturesIntermediate

Interview problems

Sliding Window Maximumhard

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related