cf.completefrontend
STACKS & QUEUES · ADVANCED

Monotonic deque

Find the maximum (or minimum) of every sliding window in one pass by keeping only the items that could still win.

Time O(n)Space O(k)7 practice problemsStep-through picture

The idea

A sliding window is a range of k items that moves one step at a time along a list. A common question asks for the biggest value in every window. Rescanning each window costs O(k) per step, O(nk) in total.

A monotonic deque does it in O(n). A deque (say "deck") is a list you can add to and remove from at both ends. It holds indexes whose values go down from front to back. The front is always the current window's maximum.

Two rules keep it that way. When an index slides out of the window, remove it from the front. When a new value arrives, first remove every smaller value from the back: those items are older and smaller, so they can never be a window's maximum again.

An everyday example

A queue of job candidates ranked by score

A team keeps a shortlist of candidates for the next 3 openings, and candidates only stay on the list for a while. When a strong candidate arrives, any weaker candidate who arrived earlier can be dropped right away: the strong one will stay on the list longer and beats them. The best candidate is always at the front, and candidates whose time is up leave from the front.

How the example maps to the code
In the exampleIn the code
The shortlistdeque, holding indexes
A candidate's time is updeque[head] <= i - k, so head++
A stronger newcomer drops weaker, older candidateswhile (nums[deque[deque.length - 1]] <= nums[i]) deque.pop()
The best candidatenums[deque[head]]

From the slow way to monotonic deque

  1. Start with the obvious way to get the maximum of every window of size k: for each window, look at all k values. That is O(nk). With n = 100,000 and k = 50,000 it is about 2.5 billion comparisons, even though neighboring windows share all but one value.
  2. A heap of the window's values helps: the top is the maximum, and each step adds one value. But removing the value that leaves the window is awkward, so you leave old values in the heap and throw them away only when they reach the top. That is O(n log n). Better, but it still keeps values that can never matter again.
  3. Here is the fact that removes them. If an older value is not bigger than a newer value, the older one can never be a window's maximum again: every future window that contains the older value also contains the newer one, which is at least as big. So when nums[i] arrives, every earlier value <= nums[i] can be dropped for good.
  4. The values that survive go down from oldest to newest, so the oldest survivor is the biggest: the window's maximum. Old survivors leave at the front when they fall out of the window, and beaten values leave at the back when a bigger one arrives. A list you can trim at both ends is a deque. That loop is the monotonic deque.

How it works

  1. Use an array deque of indexes plus a head index for its front, so removing from the front is O(1).
  2. For each i, if the front index has left the window (deque[head] <= i - k), move head forward.
  3. While the back index's value is <= nums[i], pop it: it can never be a maximum again.
  4. Push i on the back.
  5. Once the first full window is reached (i >= k - 1), the front holds its maximum: push nums[deque[head]] into result.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function windowMax(nums, k) {
  2. const deque = [];
  3. let head = 0;
  4. const result = [];
  5. for (let i = 0; i < nums.length; i++) {
  6. if (head < deque.length && deque[head] <= i - k) head++;
  7. while (deque.length > head && nums[deque[deque.length - 1]] <= nums[i]) {
  8. deque.pop();
  9. }
  10. deque.push(i);
  11. if (i >= k - 1) result.push(nums[deque[head]]);
  12. }
  13. return result;
  14. }

How fast it is

TimeO(n)
Extra memoryO(k)

Each index enters the deque once and leaves at most once, so all the removals add up to at most n. Only indexes inside the window are kept, so the deque holds at most k of them.

  • Best caseO(n)

    Values that only go up, like 1, 2, 3, 4, 5. Each new value removes the one before it, so the deque holds one index.

  • Average caseO(n)

    Mixed values. Some steps remove several entries and some none, but every index is removed at most once overall.

  • Worst caseO(n)

    Values that only go down, like 9, 8, 7, 6. Nothing is removed from the back, so the deque fills to k entries and each one expires from the front.

Common mistakes

  • Storing values instead of indexes, so you can't tell when the front item has left the window.
  • Using shift() to remove from the front, which is O(k) each time. Keep a head index or a real deque.
  • Recording a result before the first window is full. Only start when i >= k - 1.
  • Forgetting that the removed-from-front check uses <= i - k. With < i - k the window is one item too wide.

When to use it

Look for these clues in a problem:

  • The task asks for the maximum or minimum of every window of size k.
  • A variable-size window needs its maximum and minimum while it grows and shrinks.
  • A dynamic programming step needs the best value among the last k states.
  • A simpler sliding window would need to rescan the whole window at each step.

Check yourself

Answer each one in your head first, then open it.

Why does the deque store indexes rather than values?

The code must know when the front has left the window, which is a question about its position. A value alone can't say how old it is.

Why is one if enough to expire old entries from the front?

The window moves by one index per step, so at most one index leaves it, and the deque's indexes go up, so that index can only be the front.

On [5, 1, 3, 7, 2, 2, 6, 4] with k = 3, why is the fourth window's maximum 7 even though 2 arrives?

2 is smaller than 7, so it waits behind it. 7, at index 3, is still inside the window 3 to 5.

What goes wrong if the expire check is deque[head] < i - k?

An index that is exactly i - k stays, so the window is treated as k + 1 wide, and a value that already left can still be reported as the maximum.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

After each step i, the live part of the deque, from head to the end, keeps three rules. Every index in it is inside the window i - k + 1 to i. The indexes go up and the values go strictly down from front to back. And every window index that is not in the deque has a later index in the deque with a value at least as big.

Each step keeps the rules. The window moves by one, so at most one index can leave it, and since the indexes go up, that index can only be the front: one if is enough. Popping from the back every value <= nums[i] keeps the values strictly going down when i is pushed, and each popped index now has i, later and at least as big, to cover it.

Together the rules give the answer. No index outside the deque can be the maximum, because a later deque entry is at least as big. Among the deque entries, the front is the biggest. So nums[deque[head]] is the window's maximum. Each index is pushed once and removed at most once, so the whole run is O(n).

Going deeper

3 more ideas

Why the front is the window's maximum

Every index in the deque is inside the window, because old ones are removed from the front. The values go down from front to back, because each new value removes the smaller ones before joining. So the front is the largest value among the candidates. And no item outside the deque can be the maximum: each one was removed because a bigger, newer item is in the window.

Cost

Each index is pushed once and removed at most once, either from the back by a bigger value or from the front when it leaves the window. So the total work is O(n), whatever k is. The deque never holds more than k indexes.

For minimums, and for both at once

Flip the comparison to >= to keep values going up from front to back, and the front is the window's minimum. Problems such as "the longest stretch where the max and min differ by at most limit" keep two deques at once, one for the max and one for the min, and shrink the window from the left while the difference is too big.

Work it by hand

Every step in a table, with why

Find the maximum of every window of 3 in a list of 8 numbers, with a tie and two maximums that expire from the front.

nums = [5, 1, 3, 7, 2, 2, 6, 4], k = 3

Stepinums[i]Front removedBack removedDeque valuesresultWhy
105--5[]The first index joins. No window is full yet, so nothing is recorded.
211--5, 1[]1 is smaller than 5, so it waits behind it. It could still be a maximum after 5 leaves.
323-15, 3[5]1 <= 3, so 1 can never win again and leaves from the back. The first window [5, 1, 3] is full, and its front is 5.
4375 (index 0)37[5, 7]Index 0 is <= i - k = 0, so it has left the window. Then 7 removes 3 from the back.
542--7, 2[5, 7, 7]2 is smaller than 7, so it waits.
652-2 (index 4)7, 2[5, 7, 7, 7]A tie: 2 <= 2, so the older 2 leaves. The newer one stays in the window longer, so the older one is useless.
7667 (index 3)2 (index 5)6[5, 7, 7, 7, 6]Index 3 is <= 6 - 3, so 7 expires from the front. 6 then removes the last 2.
874--6, 4[5, 7, 7, 7, 6, 6]4 waits behind 6. The last window [2, 6, 4] has maximum 6.

It returns [5, 7, 7, 7, 6, 6], one maximum for each of the 6 windows. There were 8 pushes and 6 removals: 4 from the back and 2 from the front.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Monotonic dequeO(n)O(k)You need the maximum or minimum of every window, and k can be large.
Rescan each windowO(nk)O(1)k is tiny, like 3, and the simplest code matters more than speed.
Heap with lazy removalO(n log n)O(n)You need more than the maximum, such as the top few values, or the window is not a simple sliding range.

Extra memory: O(k) live entries, since only indexes inside the window stay in the deque. This array version doesn't free the entries before head, so on falling values the array itself reaches n entries. A real deque or a ring buffer of size k keeps it at O(k).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Monotonic deque and the other approaches, on a scale where each line up is 10 times more steps.
  • Monotonic deque O(n)
  • Rescan each window O(nk)
  • Heap with lazy removal O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Monotonic deque101,0001 million
Rescan each window1001 million1 trillion
Heap with lazy removal339,96620 million

Inputs that need care

5 tricky inputs
k = 1
Every window is one value. Each step expires the previous index and the result equals nums, for example [3, 1, 2] gives [3, 1, 2].
k equal to nums.length
The only full window is the whole list, at i = n - 1, so the result has one value: the overall maximum.
k larger than the list
i >= k - 1 is never true, so the function returns []. Decide whether the task wants that or the maximum of the whole list.
Equal values: [2, 2, 2], k = 2
<= removes each older 2 when the next one arrives, so the deque holds one index and the result is [2, 2]. Using < also works but keeps every copy.
An empty list
The loop never runs and the result is [].

Variations and follow-ups

Twists interviewers add

Window minimum

Flip the back check to nums[deque[deque.length - 1]] >= nums[i]. Values then go up from front to back, and the front is the window's minimum.

Longest stretch where max minus min is at most limit

Keep two deques, one for the maximum and one for the minimum, in a window that grows on the right. While the front of the max deque minus the front of the min deque is more than limit, move the window's left edge and expire fronts that fall out. Each index enters and leaves each deque once, so it is O(n).

Best of the last k states in dynamic programming

When dp[i] depends on the maximum of dp[i - k] to dp[i - 1], keep those indexes in a monotonic deque. Each dp[i] then reads the front in O(1) instead of scanning k values.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "maximum (or minimum) of each window of size k", "over the last k items", or a variable window that must know its max and min as it changes.
  • Explain the drop rule out loud: "an older value that is not bigger than a newer one can never win again, because the newer one stays in the window longer." Everything else follows from that sentence.
  • Test by hand on k = 1, on values that only go down (so fronts expire), and on equal values. Check that the expire test is deque[head] <= i - k.
  • Expect the follow-up "why is it O(n) with a while inside a for?". Each index is pushed once and removed at most once, from the back or from the front, so the removals add up to at most n.

Where frontend code uses it

The same idea in real UI code
  • A performance overlay that shows the worst frame time over the last 60 frames can keep a monotonic deque instead of rescanning 60 numbers every frame.
  • Live dashboards show "max over the last 5 minutes" for metrics such as latency, which is a sliding window maximum.
  • Rate limiters and smoothing code for scroll or pointer data use sliding windows, and the deque gives each window's peak in constant time.

Related algorithms