Skip to content
Tutorials Center
My learning

Topics

Lesson 50 of 225 ยท Stacks and Queues

Deques and Monotonic Queues

Learn the double-ended queue (deque) in Python and the monotonic queue trick that solves sliding window maximum and minimum in O(n), with traces and code.

A deque (pronounced "deck", short for double-ended queue) lets you add and remove items at both ends in O(1). It generalizes both structures you have seen so far: use only one end and it is a stack; add at one end and remove from the other and it is a queue.

That flexibility enables a powerful technique, the monotonic queue: a deque that keeps its items in sorted order by discarding items that can never matter again. It solves "maximum (or minimum) of every window of size k" in O(n), where a naive approach takes O(nยทk). It is the windowed cousin of the monotonic stack.

Deque operations

In Python, collections.deque is the deque. Its main methods:

Operation Method Cost
add at the right (back) d.append(x) O(1)
add at the left (front) d.appendleft(x) O(1)
remove from the right d.pop() O(1)
remove from the left d.popleft() O(1)
look at the ends d[0], d[-1] O(1)
index into the middle d[i] O(n)
rotate d.rotate(k) O(k)
TEXT
appendleft ->  front [ A  B  C  D ] back  <- append
popleft    <-                              -> pop
Python All four deque operations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Building a deque yourself

A deque is usually implemented as a doubly linked list (each node knows its previous and next node), or as a circular array that can wrap at both ends. Python's deque is a doubly linked list of fixed-size blocks, which keeps most operations cache friendly. That is why the middle is slow: reaching index i means walking from one end.

Example: palindrome check with a deque

A word is a palindrome if it reads the same forward and backward. With a deque you compare the two ends and shrink inward. Each pop and popleft is O(1), so the whole check is O(n).

Python Palindrome check with a deque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a simple palindrome test, slicing (s == s[::-1]) is shorter. The deque version shows the two-ended shape of the problem, and it avoids creating a reversed copy.

Sliding window maximum

Here is the main event.

Problem. Given a list nums and a window size k, return the maximum of every window of k consecutive items. For [1, 3, -1, -3, 5, 3, 6, 7] with k = 3 the windows and maxima are:

TEXT
[1  3 -1] -3  5  3  6  7     max 3
 1 [3 -1 -3] 5  3  6  7      max 3
 1  3 [-1 -3  5] 3  6  7     max 5
 1  3  -1 [-3  5  3] 6  7    max 5
 1  3  -1  -3 [5  3  6] 7    max 6
 1  3  -1  -3  5 [3  6  7]   max 7

Brute force

For each window, call max() on k items: n - k + 1 windows times k comparisons, so O(nยทk).

Heap solution (a stepping stone)

A max-heap with lazy deletion gives O(n log n). It works but is heavier than necessary.

Monotonic queue: O(n)

Observe: if a new item x arrives, every earlier item in the window that is smaller than x can never be a window maximum again. x is bigger and will stay in the window longer than they will. So we may throw them away.

Keep a deque of indexes whose values are in decreasing order from front to back. Then:

  • The front is always the index of the current window maximum.
  • For each new item at index i:
    1. Pop from the back while the back value is <= the new value (they are dominated).
    2. Append i at the back.
    3. If the front index has left the window (front <= i - k), pop it from the front.
    4. Once the first full window exists (i >= k - 1), record nums[front].
TEXT
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3     (deque holds values; shown with indexes)

i=0  v=1   dq=[1]                     (window not full yet)
i=1  v=3   pop 1 (<=3)   dq=[3]
i=2  v=-1  dq=[3, -1]                 window full -> max 3
i=3  v=-3  dq=[3, -1, -3]             front idx 1 still in window (>=1) -> max 3
i=4  v=5   pop -3, -1, 3  dq=[5]      -> max 5
i=5  v=3   dq=[5, 3]                  -> max 5
i=6  v=6   pop 3, 5       dq=[6]      -> max 6
i=7  v=7   pop 6          dq=[7]      -> max 7

Why is it O(n)? Every index is appended once and removed at most once (from the back by domination, or from the front by expiry). That is at most 2n deque operations in total. Space is O(k) because the deque never holds more than k indexes.

Python Sliding window maximum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why <= and not < when popping? With equal values, the newer one lives longer, so the older one is useless. Using <= keeps the deque strictly decreasing and a bit smaller. Using < also gives correct maxima, just with duplicates retained.

Minimum instead of maximum

Flip the comparison: pop from the back while nums[dq[-1]] >= value, which keeps values increasing, so the front is the window minimum. A common trick is to write one function and pass the comparison in.

Python Window minimum and maximum together

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Application: longest subarray with a bounded range

Problem. Find the longest contiguous subarray in which max - min <= limit. Maintain a sliding window with left and right, and use two monotonic deques to read the window's max and min in O(1). While max - min > limit, advance left. Each pointer moves only forward, so the total is O(n).

Python Longest subarray with max minus min at most limit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Application: DP speed-ups

Some dynamic-programming recurrences have the form dp[i] = value[i] + max(dp[i-k .. i-1]). The inner maximum is exactly a sliding window maximum, so a monotonic queue turns an O(nยทk) DP into O(n). See Optimising DP.

Monotonic queue vs monotonic stack

Monotonic stack Monotonic queue
Removes from the back only the back (dominated) and the front (expired)
Answers nearest greater or smaller neighbor extreme value in a window
Typical size up to n at most k
Needs a window? no yes

If there is no window limit and you want the nearest neighbor, use the stack. If old items must expire, use the queue.

Common mistakes

  • Storing values instead of indexes. You need indexes to know when the front has left the window.
  • Wrong expiry test. The front is expired when front <= i - k, equivalently front < i - k + 1. Test with k = 1 and k = len(nums).
  • Recording answers too early. Start appending results only once i >= k - 1.
  • Using list.pop(0) instead of a deque for the front removal, which silently makes the algorithm O(nยทk).
  • Forgetting that expiry removes at most one item per step, so a single if is enough there, but the domination step needs a while.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which operations does a deque support in O(1)?

    append, appendleft, pop and popleft are all constant time. Indexing the middle is O(n) in Python's deque.
  2. 2. In the sliding window maximum algorithm, why can a smaller older value be discarded when a larger one arrives?

    The newer item is both larger and leaves the window later than the older one, so the older item is dominated forever.
  3. 3. What is the time complexity of the monotonic queue solution for n items and window size k?

    Each index enters the deque once and leaves at most once, which is at most 2n deque operations.
  4. 4. How does the algorithm know the front of the deque has left the window?

    The window covers indexes i - k + 1 through i, so an index at or before i - k is outside it.
  5. 5. To track the window minimum instead of the maximum, what changes?

    Reversing the comparison keeps values increasing from front to back, so the front is the minimum.

Summary

  • A deque is a double-ended queue: O(1) adds and removals at both ends, but O(n) access to the middle.
  • A monotonic queue is a deque of indexes whose values stay sorted; it drops dominated items from the back and expired items from the front.
  • Sliding window maximum or minimum runs in O(n) time and O(k) space, versus O(nยทk) by brute force.
  • Two monotonic queues give the window range, which solves "longest subarray with max minus min at most limit".
  • Use a monotonic stack for nearest-neighbor questions and a monotonic queue when items expire.

Next: Priority Queues