Advanced 11 min read

Sliding maximum with a deque

In one line

Keep a double-ended queue of indices whose values are decreasing, so the front is always the current window's maximum and every element is pushed and popped at most once: O(n) for all windows.

What it is

Sliding Window Maximum asks for the largest value in every window of size k. A sum can be updated by subtracting the element that leaves, but a maximum cannot: when the biggest element leaves, you need to know the next biggest.

A monotonic deque solves this. It stores indices of elements that could still become the maximum of some future window, in decreasing order of value. When a new element arrives, every smaller element behind it in the deque is removed, because the new one is both larger and will stay in the window longer, so the smaller ones can never be the maximum again. The front of the deque is the maximum of the current window.

Why interviewers ask

It is a classic hard interview problem (LeetCode 239) and a building block for other hard problems, such as 'longest subarray where max - min <= limit' and 'shortest subarray with sum at least k' with negative numbers. Interviewers look for the domination argument (why removing smaller elements is safe) and the amortised O(n) proof, and they often accept a heap solution first and then ask you to improve it.

How it works

1Store indices, not values, so you can tell when an element has left the window.
2For each index i: if the front index is i - k or smaller, it is outside the window, so pop it from the front.
3While the value at the back of the deque is less than or equal to nums[i], pop from the back. Those elements are 'dominated': nums[i] is at least as big and leaves the window later.
4Push i to the back. The deque's values are now decreasing from front to back.
5Once i >= k - 1 (the first full window), the answer for the window ending at i is nums[deque front].
6Each index is pushed once and popped at most once, so the total work is O(n), no matter how many pops happen at a single step.

Worked example · nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

i = 0 (1): deque [0]. i = 1 (3): 1 <= 3, pop index 0; deque [1].
i = 2 (-1): push; deque [1, 2] (values 3, -1). Window full: max = nums[1] = 3.
i = 3 (-3): front 1 > 3 - 3 = 0, still inside. Push; deque [1, 2, 3] (3, -1, -3). Max = 3.
i = 4 (5): front 1 <= 4 - 3 = 1, expired, pop it. Pop -3 and -1 (both <= 5). Deque [4]. Max = 5.
i = 5 (3): push; deque [4, 5] (5, 3). Max = 5.
i = 6 (6): front 4 > 3, inside. Pop 3 and 5 (both <= 6); deque [6]. Max = 6. i = 7 (7): pop 6; deque [7]. Max = 7.
Output: [3, 3, 5, 5, 6, 7].

Picture it

Picture a queue of job candidates where each newcomer is stronger than some people ahead of them and will also stay longer. Anyone weaker than a newer arrival can go home: they will never be the best person in the room while the newcomer is there. The best current candidate is always at the front.

Reference code

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()        # indices; their values decrease front to back
    out = []
    for i, x in enumerate(nums):
        if dq and dq[0] <= i - k:          # front index left the window
            dq.popleft()
        while dq and nums[dq[-1]] <= x:    # smaller values can never win again
            dq.pop()
        dq.append(i)
        if i >= k - 1:                     # first full window reached
            out.append(nums[dq[0]])
    return out

collections.deque gives O(1) pops at both ends. Every index is appended once and removed at most once, so the time is O(n) and the deque holds at most k indices, O(k) space. Using <= when popping keeps the deque strictly decreasing; < also works but keeps equal values.

Key patterns

Sliding window max or min

When: Max/min of every window of size k

How: Decreasing deque for max, increasing deque for min; pop expired indices from the front.

Max minus min within a limit

When: Longest subarray where max - min <= limit (LeetCode 1438)

How: Variable window plus two deques (max and min); shrink while max - min > limit, popping fronts whose index is now left of the window.

Shortest subarray with sum >= k and negatives

When: LeetCode 862, where the simple variable window fails

How: Build prefix sums; keep an increasing deque of prefix indices; pop the front while prefix[i] - prefix[front] >= k, recording lengths.

DP over the last k states

When: dp[i] = nums[i] + max(dp[i-k..i-1]) (jump game VI, constrained subsequence sum)

How: Maintain a decreasing deque of dp indices so the best previous state is at the front.

Real-world use

Monitoring peak metrics

Dashboards show 'peak latency in the last 5 minutes' or 'max CPU in the last 60 seconds'. A monotonic deque over time-ordered samples keeps that rolling maximum updated in amortised O(1) per new sample.

Trading indicators

Indicators such as the Donchian channel and stochastic oscillators need the highest high and lowest low over the last N periods for every new bar; two monotonic deques compute both in one pass.

Image processing

Grayscale dilation and erosion (max and min filters) take the max or min over a sliding neighbourhood. Running a sliding maximum along rows and then along columns gives a cost per pixel that does not grow with the filter size; the classic van Herk / Gil-Werman algorithm reaches the same bound using block-wise prefix and suffix maxima.

Dynamic programming speed-ups

Problems where dp[i] depends on the best dp value in the last k positions (scheduling with a maximum gap, jump games with a jump limit) use a deque to cut O(n * k) down to O(n).

In a project

An SRE team wants an alert on the maximum request latency over the last 1,000 requests for each of 300 services, updated on every request, without storing sorted copies of the data.

For each service, keep a deque of (request number, latency) pairs with decreasing latency.
On each request, pop entries from the front whose request number is at least 1,000 behind, then pop smaller or equal latencies from the back, then append the new pair.
Read the front as the rolling maximum and compare it with the alert threshold.
Use a second deque with increasing values for the rolling minimum, so the dashboard can show both.

Impact: Each request costs amortised O(1) instead of O(1,000) for a rescan or O(log 1,000) for a heap, and memory is bounded by the window. The alert reacts on the exact request that pushes the peak over the limit.

Trade-offs

Use it when

You need the max or min of a moving window, for every window
A heap's O(log k) per step is too slow or you need strict O(n)
A DP transition takes the best value from a sliding range of previous states

Avoid it when

You need arbitrary range queries, not a sliding window: use a sparse table or segment tree
You need the k-th largest or a median of the window: use two heaps or a sorted structure
The window is tiny (k of 2 or 3): a direct comparison is simpler

Cost: Time O(n) amortised (each index pushed and popped at most once). Space O(k). Heap alternative: O(n log n) with lazy deletion. Brute force: O(n * k).

Common mistakes

Storing values instead of indices, so you cannot tell when the front has left the window.
Popping from the front with the wrong boundary: expired means index <= i - k.
Reading the maximum before the first window is full (i < k - 1).
Using a Python list and list.pop(0), which is O(n) per pop; use collections.deque.
Claiming the solution is O(n * k) because of the inner while loop, instead of explaining the amortised bound.

Interview questions

Quick revision

Deque stores indices; values decrease from front to back (for max).
Step: expire front (index <= i - k), pop smaller from back, push i.
Answer = nums[deque[0]] once i >= k - 1.
Each index pushed once, popped once: O(n) time, O(k) space.
Min version: increasing deque.
Heap alternative: O(n log n) with lazy deletion.
Also used for LeetCode 862 (negatives) and DP over last k states.

Check yourself

1. For nums = [4, 2, 12, 3, 1] and k = 2, what are the window maximums?

2. In the max-deque, what order are the values kept in from front to back?

3. Why do we store indices rather than values in the deque?

4. What is the overall time complexity for an array of n elements?

Fixed-size window Monotonic stack Heap basics 1D DP (climbing stairs, house robber)

Saved on this device. Create a free account to keep it on every device.

Windows with a hash map Counting subarrays: the at-most-K trick

Practise this with Sam

A real mock interview, out loud, with an honest scorecard. Free to start.

Start free