---
title: "Sliding window maximum in O(n): the monotonic deque, traced and coded"
url: https://algopath.pro/blog/sliding-window-maximum
language: en
summary: "A deque of indexes with decreasing values keeps the window maximum at the front. The steps, a traced run, Python code for max and min, related problems and the mistakes."
updated: 2026-11-20
---

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

**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.

 

## 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?

 

| Pattern | Gives | Time | Use when |
| --- | --- | --- | --- |
| Monotonic deque | Window maximum or minimum | O(n) | A fixed or growing window |
| Monotonic stack | Nearest greater neighbour | O(n) | No window, just a neighbour |
| Heap with lazy deletion | Window maximum | O(n log n) | You also need the second maximum |
| Segment tree | Maximum of any range | O(log n) per query | Arbitrary 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](/patterns/monotonic-deque) page. The neighbouring pattern lives on the [monotonic stack](/patterns/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.
