Sliding Window Maximum

Given an array nums and a window size k, the window slides from the left to the right of the array, one position at a time, always covering k consecutive elements. Return an array of the maximum in each window position.

Hints

· Stuck? Reveal one nudge at a time.

Recomputing each window's max is O(n*k) — reuse work as the window slides.

Keep a deque of indices whose values decrease, so the front is always the max.

Evict the front when it leaves the window and the back when it's dominated by a new element.

Common doubts

You need to detect when the maximum has slid out of the window, which requires knowing its position — the index.

Once a larger, more recent element arrives, any smaller earlier element can never be the maximum of a future window, so it's dead weight.

Each index is appended once and removed once across the entire scan, so total deque work is linear.

Interview follow-ups

· What an interviewer asks next.

Keep an increasing deque instead, popping back indices whose values are >= the new element.

Yes — a min/max queue built from two stacks (each augmented like a Min Stack) gives the same amortized O(1) window extreme.

Fun facts

The monotonic deque is the sliding-window upgrade of the monotonic stack — it's the standard tool for window extrema.
This exact structure computes running maxima in image processing (morphological dilation) in linear time.

Asked at

AmazonGoogleMetaMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
The maximum of each size-3 window as it slides across the array.

Example 2

Input: nums = [1], k = 1
Output: [1]
A single window containing 1.

Constraints

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

Recomputing each window's max from scratch is O(n·k). A monotonic deque of indices — kept decreasing by value — lets the window's maximum always sit at the front: you drop indices that have slid out of the window from the front, and drop smaller-or-equal values from the back. Each index enters and leaves once, so it's O(n).

Prerequisites

Before you start

· Concepts used directly in the solution.

Deque. A double-ended queue: push/pop at both front and back in O(1).

Monotonic structure. Keeping the deque's values decreasing so the front is always the maximum.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The window

“How many outputs are there?”

n - k + 1 — one maximum per window position.

“Does the deque hold values or indices?”

Indices — so you can tell when the front has slid out of the window.

The ideal opening — say it like this

I keep a deque of indices whose values decrease from front to back, so the front is always the current window's max.

Before recording, I drop the front if it's slid out of the window, and I drop smaller-or-equal values from the back when a new element arrives.

Once the window is full, the front element is the answer for that position.

Understand the problem

Worked example — nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

windows and their maxima:
[1,3,-1]=3  [3,-1,-3]=3  [-1,-3,5]=5  [-3,5,3]=5  [5,3,6]=6  [3,6,7]=7
answer: [3, 3, 5, 5, 6, 7]

Key observations

1Aha

The front is the window maximum

Because the deque is decreasing, its front is always the largest value among the indices still in the window.

2Aha

Drop out-of-window from the front, smaller from the back

Two cleanups keep the invariant: remove a front index that slid past the window, and remove back indices whose values are dominated by the incoming element.

3Aha

Linear time

Each index is added once and removed once across the whole scan, so despite the inner loop it's O(n).

Brute force vs optimal

	Max per window	Monotonic deque
Idea	Scan each window for its max	Decreasing index deque; front is the max
Time	O(n * k)	O(n)
Space	O(1)	O(k)

Full code is in the Approaches selector below.

Summary

Key takeaway

Keep a deque of indices decreasing by value. Pop the front when it slides out of the window; pop the back while it's <= the new element; push the index. Once the window is full, the front index's value is that window's maximum. O(n) time, O(k) space.

dq = deque()
for i in 0 .. n-1:
    if dq and dq.front <= i - k: pop front
    while dq and nums[dq.back] <= nums[i]: pop back
    push i
    if i >= k - 1: output nums[dq.front]