LeetCode Sliding Window Maximum: Deque Pattern

Intermediate 9 min read

What you'll learn

✓Why a monotonic decreasing deque solves window max in O(n)
✓How to evict stale indices as the window slides
✓When to push, when to pop, and what to record
✓How to talk through the invariants on a whiteboard
✓Common bugs around indices vs values

Prerequisites

•Familiarity with the [sliding window technique](/blog/sliding-window-technique)
•Basics of [arrays](/blog/arrays-introduction)

Sliding Window Maximum (LeetCode 239, Hard) asks for the max of every length-k window. A naive scan is O(n*k); a heap gets to O(n log k). The slick answer is a monotonic deque that runs in O(n) total.

The Problem

Given an array nums and an integer k, return the maximum value of each sliding window of size k.

Example:

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

Brute Force

For each window, scan all k elements.

def max_window_brute(nums, k):
    res = []
    for i in range(len(nums) - k + 1):
        res.append(max(nums[i:i+k]))
    return res

O(n*k) time. Fine for small inputs, TLE for large ones.

Optimal Solution

Maintain a deque of indices such that the values they point to are strictly decreasing. The front always holds the index of the current window’s max.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    res = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

Each index is pushed and popped at most once, so total work is O(n).

Walk Through an Example

nums = [1,3,-1,-3,5,3,6,7], k=3.

i=0: deque becomes [0].
i=1: 3 > 1, pop 0, push 1. Deque [1].
i=2: -1 < 3, push 2. Deque [1,2]. Window full, record nums[1]=3.
i=3: -3 < -1, push 3. Front index 1 still in window. Record 3.
i=4: 5 evicts 3, 2; then evict 1 since out of window? 1 is at i-k = 1, kept until i=4 makes i-k=1, so popleft. Deque [4]. Record 5.
Continue: results [3,3,5,5,6,7].

Edge Cases

k == 1: result equals nums.
k == len(nums): one window, returns the global max.
All equal values: the deque holds one or many equal entries depending on < vs <= policy; using strict < keeps duplicates, both work.
Negative numbers and zeros mix freely; comparisons handle them.

Complexity Analysis

Brute force: O(n*k) time, O(1) extra.
Heap solution: O(n log k) time, O(k) space (needs lazy deletion).
Monotonic deque: O(n) time, O(k) space.

The deque is optimal in both axes.

How to Explain It in an Interview

State the invariant first: the deque stores indices in increasing order of position, with strictly decreasing values. From that, two operations follow naturally. One, evict the front when it falls outside the window. Two, pop the back while it is smaller than the incoming value, because it can never be the max while the new value is present and newer. Walk through the first few iterations to demonstrate. Highlight amortized O(n) because each index enters and exits the deque at most once.

LeetCode 3 Longest Substring Without Repeating Characters (sliding window)
LeetCode 76 Minimum Window Substring
LeetCode 480 Sliding Window Median (heap + lazy deletion)
LeetCode 862 Shortest Subarray with Sum at Least K (deque on prefix sums)

Wrap up

Sliding Window Maximum is the canonical monotonic deque problem. Once you see the eviction rule, you’ll spot the pattern everywhere: shortest subarray with sum constraints, stock spans, next greater element. Memorize the template and adapt the comparison.