Monotonic deque window max

52 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

The numbers are 1, 3, −1, −3, 5, 3, 6, 7, and a window of width 3 slides across them. For every window position we want its maximum. The windows are [1,3,−1], [3,−1,−3], [−1,−3,5], [−3,5,3], [5,3,6], [3,6,7], and their maximums are 3, 3, 5, 5, 6, 7.

By hand you look at all 3 numbers in each window: 6 windows × 3 looks = 18 looks. For n numbers and a window of width k that is about n × k looks, which is a billion for a million numbers and a window of a thousand. The waste is that windows overlap almost completely; sliding one step only adds one number and drops one, yet we re-scan everything.

Ask a sharper question: which numbers in the window could ever be the maximum of a future window? In [1, 3, −1], the 1 cannot: the 3 is to its right, bigger, and will stay in the window at least as long as the 1. So 1 is dead. Only numbers with nothing bigger to their right inside the window matter.

Build the structure, one piece at a time

Piece 1: a deque. A deque is a line you can add to and remove from at both ends. We will keep positions (indices) in it.

Piece 2: adding at the back. When a new number arrives, remove from the back every position whose value is smaller than the new number, because they are now dead. Then add the new position at the back. After this the values in the deque, read front to back, are decreasing.

Piece 3: removing at the front. The front position is the oldest survivor. When the window slides past it (front index ≤ current index − k), remove it from the front.

Piece 4: reading the answer. Once the window is full, its maximum is the value at the front.

Why it is correct

The invariant: the deque holds indices inside the current window, in increasing order of index, with decreasing values from front to back; and every index of the window that is not in the deque has a larger-or-equal value somewhere to its right inside the window.

Front removals keep every index inside the window. Back removals only delete an index when the newcomer, which is to its right and inside the window, is bigger, so a deleted index is dominated. Adding at the back after those removals keeps the values decreasing. The window maximum is some index of the window; either it is in the deque, or it is dominated by a bigger value, which contradicts it being the maximum. So the maximum is in the deque, and since values decrease from the front, it is the front.

Why it is fast

Each index is added to the deque exactly once, and removed at most once, either from the back or from the front. The inner while loop only runs when it removes something.

additions + removals ≤ 2n, so the whole sweep is O(n), independent of k

A million numbers with a window of a thousand costs two million deque moves instead of a billion looks.

How to recognise it in an interview

The cues are "maximum (or minimum) of every window", "sliding window" together with "max/min", or a dynamic programme where each state depends on the best of the previous k states. Say: "I keep a deque of candidates that are still useful, decreasing from the front, and drop the front when it leaves the window."

Sliding Window Maximum is the example above. Jump Game VI is dp[i] = nums[i] + max of the previous k dp values, which is exactly a window max over the dp array. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit runs two deques at once, one for the window max and one for the window min.

02The idea in one line

A deque of candidates, decreasing; front is the window max; drop fronts that left the window.

Reach for it when: Sliding window max/min, shortest subarray with sum ≥ k, jump game with deque DP.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Sliding Window Maximum k=3 on [1,3,-1,-3,5,3,6,7]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Front of the deque is the window max; the back holds smaller, newer candidates
2. Add 1: push index 0 at the back
3. Add 3: drop smaller tail 1, push 1
4. Add -1: push index 2 at the back
5. Window [0..2] max = front = 3
6. Add -3: push index 3 at the back
7. Window [1..3] max = front = 3
8. Add 5: drop smaller tails -3, -1, 3, push 4
9. Window [2..4] max = front = 5
10. Add 3: push index 5 at the back
11. Window [3..5] max = front = 5
12. Add 6: drop smaller tails 3, 5, push 6
13. Window [4..6] max = front = 6
14. Add 7: drop smaller tail 6, push 7
15. Window [5..7] max = front = 7
16. Result: [3,3,5,5,6,7]
17. Each index enters and leaves the deque once: O(n)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Queue & Deque: Queue over a time window, Queue from two stacks.