Monotonic Queue

Keep a deque of candidate indexes in sorted order so the maximum or minimum of a sliding window, or of a range of earlier DP states, is always at the front. The whole scan is O(n).

Overview

The idea

A sliding window of size k moves one step at a time. Its sum is easy to keep: add the element that enters, subtract the one that leaves. Its maximum is not. When the largest element leaves, the next largest can be anywhere in the window, and finding it by scanning costs O(k) per step.

A monotonic queue keeps only the elements that could still become a window maximum, in decreasing order, in a deque (a queue that can add and remove at both ends). The front is always the current maximum. Every index enters the deque once and leaves once, so the whole scan is O(n).

Scan each window for its maximum — about 99 million comparisons — O(n·k)
Monotonic deque — at most about 200,000 deque operations — O(n)

The numbers come from (n − k + 1) · k = 99,001,000 and 2n = 200,000.

Two ends, two jobs

Each end of the deque has one job. The back keeps the order: before a new index is added, every index at the back whose value is at most the new value is removed, because an older, smaller element can never be the maximum while the new one is in the window. The front handles age: when the front index falls out of the window, it is removed.

Order — back — value at the back is at most the new value — it is older and not larger, so it can never be the maximum again
Age — front — front index is at most i − k — it is no longer inside the window

For a window minimum, flip the order rule: pop the back while its value is at least the new value, so the deque increases and the front is the minimum.

A trace

[1, 3, 5, 2, 8, 1, 4] with k = 3. The deque shows values; the code stores indexes.

0 — 1 — none — none — 1 — not yet
1 — 3 — 1 — none — 3 — not yet
2 — 5 — 3 — none — 5 — 5
3 — 2 — none — none — 5, 2 — 5
4 — 8 — 2, then 5 — none — 8 — 8
5 — 1 — none — none — 8, 1 — 8
6 — 4 — 1 — none — 8, 4 — 8

The result is [5, 5, 8, 8, 8]. No front pop happened here because every maximum was pushed out by a larger value before it aged out. With [9, 1, 1, 1] and k = 2, the 9 would be popped from the front at i = 2.

Stack or queue?

A monotonic stack and a monotonic queue share the back rule. The difference is the front. A stack never removes its oldest element, so it answers nearest-neighbor questions. A queue removes old indexes from the front, so it answers questions about a range that moves.

Removes at — the top only — both ends
Answers — the nearest greater or smaller element for each position — the maximum or minimum of each window
Example — Next Greater Element, Largest Rectangle in Histogram — Sliding Window Maximum, Jump Game VI
Space — O(n) — O(k), the window size

Why it is O(n)

The inner while loop can pop many indexes in one step, so count per index instead of per step. Each index is pushed once and popped at most once, from the back or from the front. That is at most 2n deque operations for the whole scan.

The deque never holds more than k indexes, because anything older than i − k has been popped from the front, so the space is O(k).

Indexes, not values

The front rule compares an index with i − k. A deque of values cannot tell whether its front is still inside the window, and an equal value later in the window would be indistinguishable from the old one. Store indexes and read values as nums[index].

In Python, use collections.deque. Its appends and pops from either end cost about O(1), while list.pop(0) moves every element and costs O(n). In Java, use ArrayDeque, whose main operations run in amortized constant time.

Maximum and minimum together

Some windows need both extremes at once. Longest Continuous Subarray With Absolute Diff asks for the longest window where the maximum minus the minimum is at most a limit. Keep two deques, one decreasing for the maximum and one increasing for the minimum, and a left edge that moves forward while the window breaks the limit. An index is popped from a front only when it falls behind the left edge.

The trace below runs on [8, 2, 4, 7] with limit 4.

0 — 8 — 8 — 8 — 0 — [8] — 1
1 — 2 — 2 — 2 — 1 — [2] — 1
2 — 4 — 4 — 2 — 1 — [2, 4] — 2
3 — 7 — 7 — 4 — 2 — [4, 7] — 2

At right = 1 the window [8, 2] has a gap of 6, so the left edge moves to 1 and the 8 leaves the maximum deque from the front. It had already left the minimum deque from the back, the moment the 2 arrived. The answer is 2.

Speeding up a DP

A recurrence of the form dp[i] = value[i] + best of dp[j] over the last k positions is a window maximum over the dp array. Computing the best by scanning costs O(n·k); a monotonic deque over dp indexes brings it to O(n).

Jump Game VI: from index i you may jump 1 to k steps forward, and the score is the sum of the values you land on. Then dp[i] = nums[i] + max(dp[i − k] .. dp[i − 1]).

The trace below runs on [1, -1, -2, 4, -7, 3] with k = 2.

0 — 1 — none — 1 — 0
1 — −1 — dp[0] = 1 — 0 — 0, 1
2 — −2 — dp[0] = 1 — −1 — 0, 1, 2
3 — 4 — dp[1] = 0 — 4 — 3
4 — −7 — dp[3] = 4 — −3 — 3, 4
5 — 3 — dp[3] = 4 — 7 — 5

The answer is 7: the path 1, −1, 4, 3. At i = 3, the front (index 0) has aged out, so the best in range is dp[1].

Negative numbers: prefix sums with a deque

Shortest Subarray with Sum at Least K allows negative numbers, so the usual expand and shrink window fails: adding an element can lower the sum. Use prefix sums instead. A subarray from i + 1 to j has sum P[j] − P[i], so for each j you want the largest i with P[j] − P[i] ≥ K.

Keep a deque of prefix indexes with increasing prefix values. At each j, pop from the front while P[j] − P[front] ≥ K and record j − front; a front that works now can never give a shorter answer later. Then pop from the back while P[back] ≥ P[j], because a later index with a smaller or equal prefix is a better start for every future j.

[2, -1, 2] with K = 3. The prefix sums are P = [0, 2, 1, 3].

0 — 0 — none — none — 0 — none
1 — 2 — none — none — 0, 1 — none
2 — 1 — none — 1 (P[1] = 2 ≥ 1) — 0, 2 — none
3 — 3 — 0 (3 − 0 = 3) — none — 2, 3 — 3

The answer is 3, the whole array. Each prefix index is pushed once and popped at most once, so the pass is O(n).

> [!IMPORTANT] > Say why each pop is safe. The front pop is safe because later j values only make the answer longer for that i. The back pop is safe because the new prefix is at least as small and closer to every future j.

What you will be able to do

Explain the two removal rules, one per end, and why each is safe.
Trace Sliding Window Maximum by hand and argue O(n) time and O(k) space.
Turn a dp recurrence over the last k states into a deque pass.
Keep a window's maximum and minimum with two deques.
Handle negative numbers in shortest-subarray problems with prefix sums and a deque.

When to use it

The maximum or minimum of every window of size k
A dp recurrence that takes the best of the last k states: dp[i] = value[i] + max or min of dp[i − k] to dp[i − 1]
Jump problems where each move picks the best landing spot within reach
The longest window whose maximum minus minimum stays within a limit (two deques)
Shortest subarray with a sum of at least K when numbers can be negative (prefix sums plus a deque)
Any scan where a plain sliding window would recompute a maximum or minimum over overlapping ranges

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio