Sliding Window Maximum: Monotonic Deque Mastery

LeetCode 239 Sliding Window Maximum is one of those hard problems that feels impossible until you see the trick. You are given an array of integers and a window size k. Slide the window from left to right and return the maximum value in each window position. The brute force is obvious, but the optimal solution requires a data structure you might not reach for instinctively: a monotonic deque.

The problem

Given an array nums and an integer k, return an array of the maximum value in every contiguous subarray of length k.

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

The first window is [1, 3, -1] with max 3. The second window is [3, -1, -3] with max 3. And so on. There are n - k + 1 windows total.

Why brute force is not enough

The obvious approach: for each window position, scan all k elements to find the max.

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

This runs in O(nk) time. For small k that might be fine, but when k is large (say k = 50000 on an array of 100,000 elements), the inner scan dominates and you hit time limits. The problem is that every time the window slides by one position, you recompute the max from scratch. You throw away almost everything you knew about the previous window.

What you really want is a way to track the maximum as elements enter and leave the window, updating in O(1) per step.

The monotonic deque approach

The key insight is to maintain a deque (double-ended queue) that stores indices of array elements in decreasing order of their values. Here are the rules:

1. The front of the deque is always the index of the maximum in the current window. You can read the max in O(1) by looking at nums[deque[0]].

2. When adding a new element, pop all smaller elements from the back. If nums[i] is larger than nums[deque[-1]], the element at the back can never be the max for any future window (the new element is both larger and has a later index). Pop it. Keep popping until the back of the deque holds something larger than nums[i], then push i.

3. When the front falls out of the window, remove it. If deque[0] is <= i - k, it is no longer inside the current window. Pop it from the front.

These three rules together guarantee that the deque is always a decreasing sequence of values, and the front is always the window max.

The code

from collections import deque

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

    for i in range(len(nums)):
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        dq.append(i)

        if dq[0] <= i - k:
            dq.popleft()

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Let's break it down line by line:

1. Pop smaller elements from the back. The while loop removes any index from the back of the deque whose value is <= the current element. These elements are now irrelevant because the current element is both larger and further right.

2. Push the current index. After cleaning the back, append the current index.

3. Remove the front if it is out of the window. If dq[0] is at index <= i - k, it is outside the window. Remove it with popleft.

4. Record the result once the first full window is formed. When i >= k - 1, we have seen at least k elements. The front of the deque is the max.

Notice the use of <= in the comparison nums[dq[-1]] <= nums[i]. Using <= instead of < means that when there are duplicates, we keep the rightmost occurrence. This does not affect correctness for this problem, but it keeps the deque as small as possible.

Step-by-step walkthrough

Let's trace through nums = [1, 3, -1, -3, 5, 3, 6, 7] with k = 3. The array is on the left, the deque on the right. Green numbers below the array are the output values filled in so far.

A few things to notice:

• The deque is always decreasing. The front holds the largest value, the back holds the smallest. When a new element violates this order, we pop from the back until the order is restored.
• Step 5 is the dramatic one. Value 5 at index 4 is larger than everything in the deque. It pops all three entries. This is the power of the monotonic deque: you do not scan the window, you just maintain the invariant.
• Each index is pushed once and popped at most once. Across the entire algorithm, the total number of push and pop operations is at most 2n. That is why the total time is O(n).

Complexity analysis

Time: O(n). Each of the n elements is pushed onto the deque once and popped at most once (from either end). The total work across all iterations is at most 2n operations.

Space: O(k). The deque never holds more than k elements at a time, because any element older than k positions gets removed from the front.

The building blocks

This problem is built on two reusable bricks:

1. Monotonic deque maintenance

The core pattern for maintaining a decreasing deque is:

while dq and nums[dq[-1]] <= nums[i]:
    dq.pop()
dq.append(i)

This is the same "pop smaller elements" pattern used in monotonic stacks, but applied to a deque so you can also remove from the front. The comparison direction determines whether you maintain a decreasing deque (for max queries) or an increasing deque (for min queries).

2. Window boundary check

The sliding window cleanup:

if dq[0] <= i - k:
    dq.popleft()

This removes the front element when it falls out of the window. It is the piece that makes this a sliding window problem rather than a pure monotonic stack problem. Any time you need to track a property over a fixed-size window and elements expire, this is the pattern.

Edge cases

Before submitting, verify your solution handles these:

• k equals 1. Every element is its own window max. The deque processes each element individually and outputs it immediately.
• k equals n. There is only one window. The deque finds the global max.
• All elements the same like [5, 5, 5, 5] with k = 2. Every window max is 5. The <= comparison pops duplicates, so the deque stays small.
• Strictly decreasing like [9, 8, 7, 6, 5] with k = 3. The deque grows to size k and the front is popped every step when it falls out of the window.
• Strictly increasing like [1, 2, 3, 4, 5] with k = 3. Every new element pops everything. The deque always has exactly one element.
• Negative numbers. The algorithm handles them without special cases.
• Single element nums = [42], k = 1. Output is [42].

The monotonic deque approach handles all of these without any conditional branches beyond the core logic.

From understanding to recall

You have walked through the monotonic deque solution. You understand why the front of the deque is always the window max and why the total time is O(n). But could you write this from scratch in an interview next month?

The tricky parts are not conceptual. They are the small details: using <= in the back-pop comparison, checking dq[0] <= i - k for the front expiry, and starting the output at i >= k - 1. Under time pressure, people forget the front-expiry check, use the wrong comparison direction, or mix up when to start outputting results.

Spaced repetition is built for exactly this. You practice writing the monotonic deque from scratch at increasing intervals. Each time, you rebuild the back-pop loop and the front-expiry check from memory. After a few repetitions, the pattern is locked in and you can apply it to any sliding window optimization problem without hesitation.

Related posts

• Daily Temperatures - The classic introduction to monotonic stacks. Sliding Window Maximum extends the same idea with a deque and a window boundary check.
• Minimum Window Substring - Another sliding window problem, but using frequency counts instead of a deque. Great for contrasting different window maintenance strategies.
• Sliding Window Pattern - The general sliding window template that underlies this and many other problems.

CodeBricks breaks the monotonic deque pattern into its reusable pieces and drills them individually. You type the back-pop loop and front-expiry check from scratch each time, building the muscle memory so that when you see Sliding Window Maximum in an interview, the code flows without hesitation.