We use necessary cookies to run the site (sign-in and language). If you accept, we also load Google Analytics to see which pages are used, and Google reCAPTCHA to keep spam off the contact and bug-report forms. Privacy policy

← Blog
How to prepare

Sliding window maximum in O(n): the monotonic deque, traced and coded

· 2026-11-20

Short answer. The sliding window maximum in O(n) uses a monotonic deque. The deque holds indexes whose values decrease from front to back. A new element evicts everything smaller from the back. The front leaves when it falls out of the window. The front is always the maximum of the current window.

What is the sliding window maximum?

Given an array and a number k. A window of length k slides left to right. For each position, report the maximum inside the window.

Naively you scan k elements per window. That is O(n · k). With n and k at a hundred thousand, that is ten billion operations.

The monotonic deque gives O(n). Each element enters the deque once and leaves once.

Maximum of every window of 3
maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)
nums
1
3
-1
-3
5
3
6
7
deque (index:value, front on the left, values fall toward the back)
empty
result
empty

Find the maximum of every window of 3 numbers. The deque keeps indices whose values could still become a maximum.

Speed race
Maximum of every 10 values in a row, over the same 40 numbers

Bars: the 40 values. The window is 10 long, a quarter of the array, and the size table keeps that ratio.

One operation is one comparison of two values. Every frame, each lane does the same number of operations, so the slow one falls behind.

Rescan each window O(n·k)
0 operations
Monotonic deque O(n)
0 operations

 

And with more numbers

Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.

n = 1,000
Rescan each window187K · 1.9 ms
Monotonic deque1.7K · under 1 ms
n = 100,000
Rescan each window1.9B · 19 s
Monotonic deque170K · 1.7 ms
n = 10,000,000
Rescan each window18.7T · 2.2 days
Monotonic deque17M · 170 ms

The pattern page: when to use it, and a template in six languages

How does the deque find the sliding window maximum?

  • The deque holds indexes. Their values decrease from front to back.
  • A new element arrives. While the back is smaller, pop the back. It can never be the maximum again.
  • Push the new index to the back.
  • The front fell outside the window: pop the front.
  • Once the window is full, the front is the maximum.

The key thought: an older and smaller element is useless. The new one outlives it in the window and beats it.

What does one run look like?

Array [1, 3, -1, -3, 5, 3, 6, 7], k = 3. Index 0, value 1: deque [0]. Index 1, value 3: 3 beats 1, pop 0, deque [1]. Index 2, value -1: deque [1, 2]. Window full, maximum 3.

Index 3, value -3: deque [1, 2, 3]. Front 1 is inside window 1..3, maximum 3. Index 4, value 5: pop 3, 2, 1, deque [4]. Maximum 5. Then 5, 6, 7. Answer [3, 3, 5, 5, 6, 7].

How do you write the sliding window maximum in Python?

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()                    # indexes, values decreasing
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                # back is smaller, useless now
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()            # front left the window
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

def min_sliding_window(nums, k):
    dq, out = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] >= x:   # comparison flipped
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

The minimum needs one flipped comparison. Everything else is identical.

How does the monotonic deque compare with its neighbours?

PatternGivesTimeUse when
Monotonic dequeWindow maximum or minimumO(n)A fixed or growing window
Monotonic stackNearest greater neighbourO(n)No window, just a neighbour
Heap with lazy deletionWindow maximumO(n log n)You also need the second maximum
Segment treeMaximum of any rangeO(log n) per queryArbitrary ranges, array changes

How do you solve Shortest Subarray with Sum at Least K?

The array has negative numbers. You need the shortest subarray with sum at least k. A plain window breaks on negatives. Compute prefix sums and keep a deque of indexes with increasing prefixes.

For each new prefix, look at the front. The difference is at least k: record the length, pop the front. While the back is at least the new prefix, pop the back. The monotonicity is over prefixes, not values.

How do you solve Constrained Subsequence Sum?

Find the maximum subsequence sum where neighbouring indexes differ by at most k. dp[i] equals nums[i] plus the best dp over the last k positions. That best value is what the deque provides. Time O(n) instead of O(n · k).

When does a problem need this pattern?

  • "Maximum of every window of length k."
  • "Minimum over the last k elements" inside a DP.
  • "Shortest subarray with sum at least k" with negatives.
  • "Difference between window max and min at most limit."

What mistakes break the solution?

  • Storing values instead of indexes. Then you cannot tell whether an element left the window.
  • Popping the back only on strict less-than. Duplicates pile up. The answer is right, but the deque grows.
  • Checking the front before pushing the new element. At k = 1 that loses it.
  • Using list.pop(0) instead of deque. Each removal is O(n).

How do you explain it in an interview?

Say: I keep a deque of candidates for the maximum, values decreasing. A new element makes every smaller one before it useless. The front leaves when it falls out of the window.

Give O(n): each index enters and leaves once. Then show it on five numbers.

Drill this pattern on the monotonic deque page. The neighbouring pattern lives on the monotonic stack page.

FAQ

Why not a heap?

A heap works in O(n log n), with lazy deletion of stale indexes. The deque is shorter and linear. Use a heap when you need several top values.

What if the window is bounded by a condition, not a length?

Same deque. The left edge moves by the condition. The front pops while its index is below the left edge. That solves the max-minus-min problem.

Can you keep two deques at once?

Yes. One for the maximum, one for the minimum. Both update every step. That gives the window's range in O(n).

Where does this show up in real systems?

Monitoring: peak load over the last minute. Finance: the highest price over the last n days. Signal processing: a max filter over a window.