Sliding Window Maximum Using Deque

Advanced 18 min read

What you'll learn

✓Why a monotonic deque solves sliding window max in O(n)
✓How the deque maintains a decreasing order of useful elements
✓Sliding window minimum as a dual problem
✓Applications in stock analysis and signal processing

Prerequisites

•Queue and deque basics — see Queues & Deques Deep Dive

Monotonic deque tracking sliding window maximum

Given an array and a window size k, find the maximum element in each window as it slides from left to right.

The Problem

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

Window           Max
[1, 3, -1]       3
[3, -1, -3]      3
[-1, -3, 5]      5
[-3, 5, 3]       5
[5, 3, 6]        6
[3, 6, 7]        7

Brute Force — O(nk)

For each window, scan all k elements:

def max_sliding_window_brute(nums, k):
    return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]

Monotonic Deque — O(n)

Maintain a deque of indices where the values are in decreasing order. The front of the deque is always the maximum of the current window.

from collections import deque

def max_sliding_window(nums, k):
    """
    Find maximum in each sliding window of size k.
    Time: O(n), Space: O(k)
    """
    dq = deque()  # Indices, values in decreasing order
    result = []

    for i, num in enumerate(nums):
        # Remove elements outside the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove elements smaller than current (they'll never be max)
        while dq and nums[dq[-1]] <= num:
            dq.pop()

        dq.append(i)

        # Window is fully formed
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Trace

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

i=0, num=1:  dq=[0]         (push 0)
i=1, num=3:  dq=[1]         (pop 0 since 1<3, push 1)
i=2, num=-1: dq=[1,2]       (push 2) → max=nums[1]=3
i=3, num=-3: dq=[1,2,3]     (push 3) → max=nums[1]=3
i=4, num=5:  dq=[4]         (pop all since 5>all, remove 1 as out of window) → max=5
i=5, num=3:  dq=[4,5]       (push 5) → max=nums[4]=5
i=6, num=6:  dq=[6]         (pop all since 6>all) → max=6
i=7, num=7:  dq=[7]         (pop all since 7>all) → max=7

Result: [3, 3, 5, 5, 6, 7]

Why Monotonic Decreasing?

Elements smaller than the current element can never be the window maximum while the current element is in the window. So we discard them. The deque front is always the largest element still in the window.

Sliding Window Minimum

Just flip the comparison:

def min_sliding_window(nums, k):
    dq = deque()
    result = []

    for i, num in enumerate(nums):
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        while dq and nums[dq[-1]] >= num:  # Changed <= to >=
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Complexity

Metric	Value
Time	O(n) — each element enters and leaves deque once
Space	O(k) — deque holds at most k elements

Edge Cases

k = 1 — every element is its own window max
k = n — single window, return overall max
All same elements — every window max is the same
Sorted ascending — deque always has one element
Sorted descending — deque grows to k elements

When to Use Monotonic Deque

Sliding window min/max
Shortest subarray with sum ≥ k (deque for prefix sums)
Jump Game VI (DP + sliding window max)
Constrained subsequence sum

Sliding Window Maximum (LeetCode 239)
Shortest Subarray with Sum at Least K (LeetCode 862)
Jump Game VI (LeetCode 1696)
Longest Continuous Subarray with Abs Diff ≤ Limit (LeetCode 1438)