Sliding Window Maximum

Six windows, one linear scan: a deque of decreasing indices keeps the current window's maximum sitting at its front.

The memory hook

Keep only future champions: discard what's smaller, evict what's stale, read the front.

HardMonotonic dequeO(n) timeO(k) space

Why a deque beats rescanning

intuition

Brute force rescans all k elements per window. But most of those elements are irrelevant: anything smaller and older than a newcomer can never be any future window's maximum, and anything outside the window is already dead. The deque stores exactly the survivors — indices in order, values decreasing.

1Evict staleIf the front index has slid out of the window, drop it from the left. It can never return.

2Stay decreasingWhile the back value is smaller than the newcomer, pop it. The newcomer is larger and newer, so it dominates.

3Read the frontOnce the window is full, the front — largest of the survivors — is the answer for this window.

The one sentence to remember: every index leaves the deque the moment it stops being useful — stale ones by position, smaller ones by domination — so whoever remains at the front is the largest value still inside the window.

Watch the deque track each window

playable trace

Start with the canonical [1, 3, −1, −3, 5, 3, 6, 7], k = 3. Step slowly and watch indices get evicted or popped exactly when they stop mattering — then try the falling preset, where almost nothing survives.

Playable trace · monotonic deque

Frames are generated from the same logic as the code below.

Presets

Current event

Ready — press Play

Window maximums

—

deque · front = max

The deque starts empty. Each step evicts stale indices from the front, pops smaller values from the back, then pushes the newcomer.

unread current in deque evicted / popped window max

0 / 0 speed 650ms

Short code, explicit boundaries

the solution

Python · monotonic deque

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()  # indices, values decreasing, all inside the window
    ans = []
    for i, x in enumerate(nums):
        if dq and dq[0] <= i - k:  # front slid out of the window
            dq.popleft()
        while dq and nums[dq[-1]] < x:  # newcomer dominates the back
            dq.pop()
        dq.append(i)
        if i >= k - 1:  # window [i-k+1, i] is full
            ans.append(nums[dq[0]])
    return ans

Ties keep the older index (strict < pop): it answers earlier windows first and leaves on schedule anyway.

Stale boundarydq[0] <= i - kThe front index is a full window behind — popleft before pushing the newcomer.

Domination rulenums[dq[-1]] < xPop the back while it is smaller; the newcomer is larger and newer, so it outlives everything it pops.

Answer readans ← nums[dq[0]]Recorded only once the window is full (i ≥ k−1), giving exactly n−k+1 answers.

Why is the front always the maximum? The deque holds in-window indices in decreasing value order: eviction removes anything left of the window, and the pop loop removes anything smaller than a newer arrival. Every in-window index is therefore either sitting behind the front (hence no larger than it) or was removed as dominated — and a dominated index always has its larger, longer-lived dominator still ahead of it.

TimeO(n)each index is appended once and removed at most once

SpaceO(k)the deque never holds more indices than fit in one window

Two quick mental checks

make it stick

[1, 3, −1, −3, 5, 3, 6, 7], k = 3

[3, 3, 5, 5, 6, 7]

When 5 arrives at index 4 it pops −3 and −1 from the back, and index 1 has slid out of the window — so the front becomes 5. Each window's answer is simply whatever sits at the deque front.

[1], k = 1

[1]

The smallest valid input: nothing to evict, nothing to pop — index 0 is pushed and the single full window reads the front. Also confirms the answer length is n−k+1 = 1.

What to say out loud

“I keep a deque of indices with decreasing values, all inside the current window. For each new element I evict the front if it slid out, pop the back while it is smaller than the newcomer, then push. Once the window is full the front is always its maximum. Each index is pushed and popped at most once, so it runs in linear time with O(k) extra space.”