Sliding Window Maximum With a Monotonic Deque

If you interview at Amazon, Google, Uber, expect some version of "Sliding Window Maximum". It is rated Hard, and it falls squarely into the Sliding Window pattern — pattern-first preparation beats grinding random problems every time. Part 10 of 11 in the Sliding Window arc.

The Problem

Given an integer array nums and window size k, return the maximum of each contiguous window of size k as it slides left to right. A max, unlike a sum, cannot be updated by simple subtraction when its element leaves — which is precisely what makes this hard and worth asking.

Input:  nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]

Recognizing the Sliding Window Pattern

Sliding window maintains a contiguous range over an array or string and slides its boundaries instead of recomputing from scratch. Fixed-size windows update a running aggregate in O(1) per step; variable-size windows grow the right edge and shrink the left only when a constraint breaks. Any problem asking about the best contiguous subarray or substring under a constraint should trigger this pattern.

A non-invertible window aggregate (max, min) is the cue for a monotonic deque: keep candidate indices in decreasing value order, so the front is always the current window's max and expired or dominated candidates are discarded exactly once.

The Approach

The deque stores indices, values decreasing. New element arriving: pop the back while its values are smaller or equal — those elements are dominated and can never be a future max. Pop the front if its index slid out of the window. The front is the answer for every completed window.

Each index is pushed once and popped at most once, so the whole thing is O(n) amortized — a heap gets you O(n log n) with lazy deletion and is the honorable fallback if the deque escapes you live.

Python Solution

from collections import deque


def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """Maximum of each length-k window, via monotonic deque of indices."""
    dq: deque[int] = deque()   # indices, values strictly decreasing
    result = []
    for i, v in enumerate(nums):
        while dq and nums[dq[-1]] <= v:
            dq.pop()                    # dominated: smaller and older
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()                # front expired out of the window
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Complexity

• Time: O(n) — amortized — every index is pushed and popped at most once
• Space: O(k) — the deque never holds more than k indices

Interview Tips and Follow-Ups

• Store indices, never values — expiry ('is the front still inside the window?') is unanswerable with values alone.
• Duplicates: popping on smaller-or-equal keeps one copy and stays correct; popping strictly-smaller also works. Pick one and defend it.
• Sliding window minimum, and the deque inside Shortest Subarray with Sum at Least K, are the two standard escalations.

That wraps part 10 of the Sliding Window arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.