LESSON 10 · PATTERN GUIDE

Monotonic Queue / Deque

Maintain only useful candidates in a deque to answer moving-window minimum or maximum queries.

FIRST, LEARN THE PATTERNKeep candidate indices ordered by value. Remove expired indices from the front and dominated values from the back.

The prompt asks for a maximum or minimum for every fixed-size window, or a shortest range with a prefix-sum condition.

How to approach it

Before reading each answer, expire indices outside the window; while the new value dominates the back, remove that candidate.

Watch out for

Store indices, not only values, so duplicates can expire at the correct time.

A CLOSER EXPLANATION

A deque keeps only candidates that could still become the answer for a future window. Older indices expire at the front; values dominated by a newer, better value are removed from the back. Each index enters and exits once, yielding O(n) total work rather than sorting every window.

NOW YOU TRY

Practice question

Find each length-3 window maximum in [1, 3, -1, -3, 5, 3, 6].

EXAMPLEvalues = [1, 3, -1, -3, 5, 3, 6], window = 3Give your answer before revealing the explanation.

Show a hint

The deque front is the maximum index for the current window.

Show an answer

[3, 3, 5, 5, 6]

CONNECT IT TO REAL LIFE

Monotonic Queue / Deque at work

A sensor reports [3, 8, 4, 6, 7]. What is the highest reading in each consecutive 3-minute window?

Show one possible approach

[8, 8, 7]. The windows are [3,8,4], [8,4,6], and [4,6,7]. Keep candidate maxima in a decreasing deque and expire old indices.

Practice next

Use these problem IDs to find additional practice for this pattern:

2398621425143814991696