Sliding window maximum

Keep a deque of indices whose values are decreasing. When a new value arrives, everything smaller behind it is discarded — those can never be a maximum again, because the newcomer is bigger and outlives them. The front is always the current window's maximum. O(n) total.

Lists & arraysCoding problemHard

Step through it

What to watch

  • Smaller values behind a larger one are discarded immediately.
  • The front is the answer without any scanning.
  • Indices are stored, not values — that is how expiry is detected.

Say this out loud

"Monotonic deque of indices, values decreasing. A new value evicts everything smaller from the back, because they can never win again. The front is the answer, and I drop it once it falls out of the window. Every index is pushed and popped once, so O(n)."

Overview

For every fixed-size window, report its maximum. A decreasing deque of indices discards smaller candidates from the back and expired indices from the front, so each value enters and leaves once.

In this guide
  1. Run it: Sliding window maximum in code
  2. Why a heap is not quite enough
  3. The monotonic deque
  4. Tracing it
  5. The observation that does the work
  6. Why indices rather than values
  7. Why it is O(n), not O(n·k)
  8. Details that matter
  9. The pattern beyond this problem
  10. Alternatives worth naming
  11. Sources and next steps

Run it: Sliding window maximum in code

The deque version with its total push and pop counts against the recompute-every-window version, on an input sized to make O(n) against O(n·k) unmistakable.

1Python
Output
2Python
Output

Why a heap is not quite enough

The natural first thought is a max-heap. It gives the maximum in O(1), and removing the element that just left the window is the problem — a heap cannot delete an arbitrary element efficiently.

The usual workaround is lazy deletion: push (value, index) and, before reading the top, discard entries whose index has fallen out of the window.

3Python
Output

O(n log n), and the heap can grow to n entries. Correct, and worth stating as the intermediate step — then improving on it.

The monotonic deque

Keep a deque of indices whose values are in decreasing order. The front is always the maximum of the current window.

Two rules, applied per element:

Evict from the front if the index there has slid out of the window. Evict from the back while the value there is less than or equal to the incoming value — those elements can never be a maximum again, because the newcomer is at least as large and stays in the window longer.

4Python
Output

O(n) time — each index is appended once and popped at most once — and O(k) space, since the deque never holds more than one window's worth of indices.

The second rule is the one that needs justifying, and the justification is short: if a later element is at least as large as an earlier one, the earlier one is dominated. It will leave the window first and it is not bigger, so no future window will ever report it as the maximum. Discarding it loses nothing.

Store indices, not values. The front-eviction rule needs to know when an element entered, and values alone cannot tell you that.

Tracing it

[1, 3, -1, -3, 5, 3, 6, 7], k = 3. The deque is shown as values for readability:

inumAfter back-evictionDequeOutput
01—[1]—
13popped 1[3]—
2−1—[3, -1]3
3−3—[3, -1, -3]3
45popped −3, −1, 3[5]5
53—[5, 3]5
66popped 3, 5[6]6
77popped 6[7]7

At i = 4 three elements are discarded at once, and the total number of pops across the whole run is still bounded by n — which is the amortisation argument that makes the nested while loops linear.

The observation that does the work

If a[j] comes before a[i] and a[j] ≤ a[i], then a[j] can never be the maximum of any future window — every window containing it from now on also contains the bigger, later a[i]. So it can be thrown away the moment a[i] arrives.

What survives is a decreasing sequence, and its front is the maximum of the current window by construction. No scan is ever needed.

Why indices rather than values

The front must be discarded once it falls out of the window, and that needs its position. Storing values leaves no way to tell an expired maximum from a current one.

The expiry check is dq[0] <= i - k — the front is older than the window's left edge. This is the other place an off-by-one lives, and it is worth writing out the first window's indices to check it.

Why it is O(n), not O(n·k)

The inner while can pop several entries in one iteration, which looks quadratic. But each index is pushed exactly once and popped at most once across the entire run, so the total pops are bounded by n.

The alternatives are worth naming: recomputing max per window is O(n·k), and a heap is O(n log k) and needs lazy deletion because you cannot remove an arbitrary element. The deque beats both.

Details that matter

<= or < in the back-eviction? Both give correct maxima. Using <= discards equal values and keeps the deque smaller; using < retains duplicates, which matters only if you need to know how many copies of the maximum are present. For this problem, <=.

Why if i >= k - 1? The first complete window ends at index k−1. Emitting earlier reports maxima of partial windows — which is sometimes the requirement, so it is worth confirming.

The output length is n - k + 1. Checking that is a fast way to catch off-by-one errors.

What if k > n? There is no complete window. Return an empty list, or the maximum of everything — ask rather than guess.

What if k = 1? The output is the input, and the code handles it: each element evicts its predecessor immediately.

The pattern beyond this problem

A monotonic deque or stack applies whenever a problem asks for an extreme value over a moving range, or for the "next greater/smaller" element.

ProblemStructureOrder
Sliding window maximumDequeDecreasing
Sliding window minimumDequeIncreasing
Next greater elementStackDecreasing
Daily temperaturesStackDecreasing
Largest rectangle in histogramStackIncreasing
Trapping rain waterStackDecreasing
Shortest subarray with sum ≥ k (with negatives)DequeIncreasing prefix sums
Jump game with a bounded jumpDequeDecreasing DP values

The shared shape: maintain a structure in which elements that can never again be the answer are discarded immediately. Once that is the framing, deciding which side to evict from and in which order follows from the specific question.

Constrained-DP problems are where this earns the most. "Maximum sum of a subsequence with no two elements more than k apart" is a DP whose recurrence needs a window maximum of previous states — the deque turns O(nk) into O(n).

Alternatives worth naming

Sparse table or segment tree. O(n log n) preprocessing and O(1) or O(log n) per query. Overkill here, since the windows are contiguous and only slide forward, and the right answer when queries are arbitrary ranges instead.

Two-pass block partitioning. Split the array into blocks of size k, compute prefix maxima within each block from the left and suffix maxima from the right, and every window's maximum is the max of two precomputed values. O(n) time, O(n) space, and no deque — an elegant answer that surprises interviewers.

max() per window. O(nk), and genuinely the right choice when k is small and clarity matters.

Sources and next steps

How the code works

The deque version with its total push and pop counts against the recompute-every-window version, on an input sized to make O(n) against O(n·k) unmistakable.

How the code works

  1. while dq and values[dq[-1]] <= v: dq.pop()The eviction. Anything smaller sitting behind a newer, larger value is permanently useless, because every future window holding it also holds the newcomer.
  2. dq[0] <= i - kExpiry by position, which is why indices are stored rather than values. Storing values leaves no way to tell a stale maximum from a live one.
  3. out.append(values[dq[0]])No scan. The deque is decreasing by construction, so its front is the window maximum — that is the entire payoff.
  4. pushes and popsEach index enters once and leaves at most once, so the totals are bounded by n however aggressive the inner loop looks. That is the amortised argument, measured.

Change one thing

  • Set k = 1. The deque never holds more than one entry and the answer is the input — a good sanity check on the expiry condition.
  • Change <= to < in the eviction. Equal values are now kept, which is still correct and grows the deque for no benefit.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Check yourself

0 of 3

Answer without scrolling back up.

  1. Why can a smaller value behind a larger one be discarded?

  2. Why store indices in the deque rather than values?

  3. The algorithm is O(n) rather than O(n·k) because:

Cheat sheet

Sliding window maximum

Track the maximum in a sliding window using a monotonic deque. Watch old and small values drop as the window advances, keeping every lookup O(1).

INTERVIEW · vizlearn.in/interview/sliding-window-maximum.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.