239. Sliding Window Maximum

239

HardSliding WindowDeque of indicesMonotonic decreasing deque

Sliding Window Maximum

Given an integer array nums and a window size k, the window of k consecutive elements slides from the left end to the right end one position at a time. Return an array of the maximum value inside the window at each position.

Open official problem prompt ↗

In plain English

Produce the maximum of every contiguous block of k elements as the block slides across the array, in linear total time.

Picture it like this

Think of people queued by height at a viewpoint. Whenever a taller person arrives, everyone shorter behind them steps aside because they will be blocked from view for as long as the tall person stays. The tallest still in the viewing zone stands at the front.

Example

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Why: The successive windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7], whose maxima are 3,3,5,5,6,7.

Constraints

1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length

Pattern lesson

See the pattern, then code

Monotonic decreasing deque

↗

Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. A smaller element that appears before a larger element can never be a future maximum while the larger one is still in the window, so it can be discarded permanently. Keep indices in a deque whose values are strictly decreasing; the front is always the current maximum.

New words, made simpleKnow these before the algorithm

Deque: A double-ended queue supporting O(1) push/pop at both ends.
Monotonic deque: A deque kept in sorted order (here strictly decreasing by value) by evicting elements that violate the order.
Dominated element: An earlier element that is no larger than a later one; it can never again be the window maximum.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Recompute each window

Too slow for n up to 10^5 with large k.

For every window position scan all k elements to find the max.

Time O(n*k)Space O(1)

Max-heap of (value, index)

Works but carries a log factor and lazy-deletion bookkeeping.

Push each element; pop the top while its index is out of the window.

Time O(n log n)Space O(n)

Best choiceMonotonic decreasing deque

Each index is pushed and popped at most once, giving true linear time.

Keep indices whose values decrease; front is the max, evict dominated and expired indices.

Time O(n)Space O(k)

The rule we keep true

Invariant

After processing index i, the deque holds a strictly decreasing sequence of values whose indices all lie within the current window, and its front is the window's maximum.

Why this is correct

Reasoning

Every index enters the deque exactly once and leaves at most once, so total work is linear. Popping smaller trailing values is safe because while a larger value remains in the window it is always a better candidate; popping an expired front is safe because it can no longer belong to any current or future window.

The algorithm in three movesSay these aloud before coding

1Before adding index i, pop from the back every index whose value is <= nums[i] (they are dominated)

i=3: deque holds indices [1,2,3] -> values [3,-1,-3]

2Append i to the back

front index 1 is inside window [1..3], max = 3

3Pop the front if it has slid out of the window (front <= i - k)

i=4 (value 5): pop 3, 2, 1, deque = [4]

4Once i >= k - 1, record nums[front] as this window's maximum

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

-12

-33

1 · Readx=1

2 · AskAny smaller tail to evict?

3 · Update statedeque=[0]

4 · ResultNo output yet (window not full).

Key takeaway

The window over indices 1-3; the deque front (index 1, value 3) is the window maximum.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-8Evict dominated tail
Remove every trailing index whose value is <= the incoming value; they can never win again.
2
Lines 9-11Append and drop expired front
Add the new index, then discard the front if it has slid past the window's left edge.
3
Lines 12-13Emit the maximum
Once the first full window is formed, the front index always holds the current maximum.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

k == 1 returns the array unchanged
k equals the array length gives a single global maximum
all-equal elements (the <= comparison still keeps the deque size bounded)
strictly increasing or strictly decreasing arrays

Common beginner mistakes

Storing values instead of indices, which makes it impossible to detect when the front expires
Using < instead of <= when evicting, leaving stale duplicate indices that never expire correctly
Comparing dq[0] with i-k using the wrong boundary (off-by-one on the window edge)
Emitting output before the first window is complete (i < k-1)

Check your understanding

Why is it correct to permanently discard an element as soon as a later, larger element arrives?

Sliding Window Maximum

Sliding Window Maximum

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Sliding Window