Monotonic deques

What is a queue?

A queue is a collection where you add at the back and remove from the front. Enqueue means add an item; dequeue means remove the oldest waiting item. This order is called first in, first out, or FIFO. A deque lets you add and remove at either end.

Example: Enqueue 4, then 8, then 15. The next dequeue returns 4. The remaining queue is 8, 15.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays

Understand the idea

A monotonic deque retains only candidates that can become a future maximum. Expire old indices from the front; remove dominated values from the back; the front gives the current maximum.

Work through an example

A new 5 makes earlier 3,-1,-3 useless: it is larger and expires later. A smaller new value stays behind the current maximum as a future candidate.

Time and space complexity

O(n) total work/O(k) candidate storage, plus O(n-k+1) output.

Why it works

Indices increase; their values decrease; every index is inside the live window.

Common mistakes

Store indices to expire values correctly.
Duplicate-value policy must be consistent; <= keeps the newer equal candidate.

Chapter lab · Python implementation

Queues process the oldest pending item first. Python deque supports efficient operations at both ends; list.pop(0) shifts a packed list. The lab maintains a decreasing deque of candidate indices for each fixed-size window maximum, keeping expiration separate from dominance.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from collections import deque

def window_max(values,k):
    if not 1<=k<=len(values):
        raise ValueError('invalid k')
    candidates=deque()
    output=[]
    for i,x in enumerate(values):
        while candidates and candidates[0]<=i-k:
            candidates.popleft()
        while candidates and values[candidates[-1]]<=x:
            candidates.pop()
        candidates.append(i)
        if i>=k-1:
            output.append(values[candidates[0]])
    return output

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert window_max([1,3,-1,-3,5,3,6,7],3)==[3,3,5,5,6,7]
assert window_max([2,2,2],2)==[2,2]
assert window_max([-4],1)==[-4]

CHECK YOUR UNDERSTANDING

What is a queue?

First candidate.