LeetCode 239 Sliding Window Maximum: The Monotonic Deque, Explained Properly

Sliding Window Maximum is the problem that introduces the monotonic deque, a data structure that answers "max of the last k elements" in amortised O(1). It is LeetCode 239, tagged Hard, and appears in Blind 75-style lists and in interview loops at companies such as Amazon, Google and Microsoft. The code is under 15 lines. What interviewers actually test is whether you can explain why throwing elements away is safe and why the nested loop is still linear. This guide answers both, dry-runs the deque step by step, and compares it with the heap and block-based solutions.

The Problem: Maximum of Every Window of Size k

Given an integer array nums and a window size k, slide the window from the left end to the right end one position at a time and return the maximum of each window. There are n - k + 1 windows. Constraints: 1 <= n <= 10^5, -10^4 <= nums[i] <= 10^4, 1 <= k <= n.

The difficulty compared with a sliding window sum: a sum can be updated in O(1) by adding the new element and subtracting the old one. A maximum cannot be "un-added". When the current maximum leaves the window, you need to know the next largest element, and the one after that.

Brute Force, and What It Wastes

Scan each window: O(k) per window, O((n − k + 1) · k) overall, which is O(n·k). With n = 10⁵ and k = 5 × 10⁴, that is around 2.5 × 10⁹ comparisons. Too slow.

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

The waste: consecutive windows share k − 1 elements, and the brute force re-examines all of them. Worse, it keeps re-examining elements that can never be the answer again. That second observation is the key to the optimal solution.

The Dominance Insight: Some Elements Are Useless Forever

Suppose j < i and nums[j] <= nums[i]. Element j entered the window earlier, so it will also leave earlier. While both are in the window, i is at least as large. After j leaves, it does not matter. So there is no future window in which j is the unique maximum. Element j is dominated, and we can discard it permanently the moment i arrives.

Picture people standing in a queue to see over a wall, where each person's value is their height and people leave from the front as time passes. If a taller person stands behind a shorter one who will leave first, the shorter one will never be the tallest visible person again. That is why the candidates form a "descending staircase".

The Deque Invariant

We store candidate indices in a double-ended queue dq and maintain two properties at the end of each step:

1. Window property. Every index in dq lies in the current window [i - k + 1, i].
2. Monotonic property. Values are strictly decreasing from front to back: nums[dq[0]] > nums[dq[1]] > .... Indices are increasing front to back.

Together they guarantee that the front of the deque holds the maximum of the current window: every non-candidate in the window has been dominated by something still in the deque, and the deque is sorted with its largest value at the front.

Each step does four things, in this order:

1. Expire. If dq[0] <= i - k, pop it from the front. At most one index expires per step, because the window moves by one.
2. Dominate. While the back's value is <= nums[i], pop it from the back. These are older and not larger, so they are useless.
3. Push. Append i to the back.
4. Read. If i >= k - 1 (the first full window is complete), the answer for this window is nums[dq[0]].

Why a deque and not a stack? We remove from both ends: from the back when a dominating element arrives (stack-like) and from the front when the oldest candidate expires (queue-like). A monotonic stack, which you may know from Next Greater Element, only supports the back. If monotonic stacks are new to you, read stack, queue and monotonic stack problems first; this is the same idea with an expiry rule added.

Sliding Window Maximum Code in C++, Java and Python

#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;              // indices, values strictly decreasing
        vector<int> result;
        result.reserve(nums.size() - k + 1);
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (!dq.empty() && dq.front() <= i - k) dq.pop_front();    // expire
            while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back(); // dominate
            dq.push_back(i);
            if (i >= k - 1) result.push_back(nums[dq.front()]);
        }
        return result;
    }
};

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
            dq.offerLast(i);
            if (i >= k - 1) result[i - k + 1] = nums[dq.peekFirst()];
        }
        return result;
    }
}

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()          # indices; nums[dq] strictly decreasing
        result = []
        for i, x in enumerate(nums):
            if dq and dq[0] <= i - k:
                dq.popleft()
            while dq and nums[dq[-1]] <= x:
                dq.pop()
            dq.append(i)
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result

In Java, ArrayDeque is the right choice: Stack is a legacy synchronised class and LinkedList allocates a node per element. Comparing dq.peekFirst() <= i - k auto-unboxes the Integer to int, so it is safe; comparing two Integer objects with == would not be.

Does the order of "expire" and "dominate" matter?

Not for correctness. If the front index has expired and the new element is larger, the dominate loop may pop it from the back first (when the deque has one element, front and back are the same). If it is not popped there, the expire check removes it. The only hard requirement is that expiry is checked before you read the front. Doing expire first is the conventional order and the easiest to explain.

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

The deque column shows index:value pairs from front to back.

Output [3, 3, 5, 5, 6, 7]. Look at step 3: the deque is [3, -1, -3], a perfect descending staircase. It holds the current max and the "successors" that would take over as older elements expire. At step 4, index 1 (value 3) expires, and the new value 5 dominates everything else, so the deque collapses to a single element.

A second trace: decreasing input

For nums = [9, 8, 7, 6, 5], k = 3, nothing is ever dominated. The deque grows to [9, 8, 7], then each step expires one from the front and pushes one at the back: [8, 7, 6], [7, 6, 5]. Output [9, 8, 7]. This is the case that exercises the expiry rule; an implementation that forgets it outputs [9, 9, 9]. Always test a strictly decreasing array.

Why It Is O(n): The Amortised Argument

The while loop can pop many elements in one step (step 4 above popped two from the back plus one from the front). So a single step is not O(1). But count operations over the whole run:

• Each index is pushed exactly once: n pushes.
• Each index is popped at most once, from either end, because once it is popped it is gone: at most n pops.

Total deque work is at most 2n, so the algorithm is O(n) time regardless of k. The deque never holds more than k indices (all must be in the window), so extra space is O(k), plus O(n − k + 1) for the output.

The Heap Alternative (and Why It Is Second Best)

The most natural "better than brute force" idea is a max-heap. The difficulty is deletion: heaps do not support removing an arbitrary element efficiently. The standard trick is lazy deletion: store (value, index) pairs and, before reading the top, pop any entries whose index has left the window.

import heapq

def max_sliding_window_heap(nums, k):
    heap, result = [], []                 # Python heapq is a min-heap: store -value
    for i, x in enumerate(nums):
        heapq.heappush(heap, (-x, i))
        if i >= k - 1:
            while heap[0][1] <= i - k:    # top is outside the window
                heapq.heappop(heap)
            result.append(-heap[0][0])
    return result

import java.util.PriorityQueue;

class SolutionHeap {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // max-heap by value; ties broken arbitrarily
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            pq.offer(new int[]{nums[i], i});
            if (i >= k - 1) {
                while (pq.peek()[1] <= i - k) pq.poll();
                result[i - k + 1] = pq.peek()[0];
            }
        }
        return result;
    }
}

Complexity: stale entries are only removed when they reach the top, so the heap can grow to O(n). With an increasing array, the newest element is always on top, so expired entries never surface and all n stay in the heap. Each push and pop is O(log n), giving O(n log n) time and O(n) space. In C++, a std::multiset with explicit erase of the outgoing element gives O(n log k) and O(k) space, because it supports arbitrary deletion.

When to use it in an interview: if you cannot recall the deque, the heap is a solid answer that most interviewers will accept as a stepping stone, then ask you to optimise. Present it as "O(n log n), and I believe we can do O(n) by noticing that smaller older elements are useless". For more heap patterns, see heap and priority queue interview problems and LeetCode 215 Kth Largest Element.

Another O(n) Solution: Block Prefix and Suffix Maxima

This approach is less known and makes a strong impression when offered as an alternative. Split the array into blocks of size k: indices [0, k-1], [k, 2k-1], and so on. Compute:

• left[i]: max from the start of i's block up to i (prefix max within the block).
• right[i]: max from i to the end of i's block (suffix max within the block).

Any window [i, i + k - 1] of length exactly k either aligns with one block or straddles two adjacent blocks. In both cases, its maximum is max(right[i], left[i + k - 1]): right[i] covers the part of the window in the first block, and left[i + k - 1] covers the part in the next block.

def max_sliding_window_blocks(nums, k):
    n = len(nums)
    left, right = [0] * n, [0] * n
    for i in range(n):
        left[i] = nums[i] if i % k == 0 else max(left[i - 1], nums[i])
    for i in range(n - 1, -1, -1):
        if i == n - 1 or (i + 1) % k == 0:
            right[i] = nums[i]
        else:
            right[i] = max(right[i + 1], nums[i])
    return [max(right[i], left[i + k - 1]) for i in range(n - k + 1)]

O(n) time, O(n) space, no deque, and every step is a simple array scan, which is friendly to vectorisation and parallel processing. The deque uses less memory (O(k)) and works on a stream, where you cannot scan backwards. That trade-off, "streaming versus whole-array", is the kind of discussion that distinguishes senior candidates.

If the interviewer generalises to "answer max queries over arbitrary ranges", none of the window-specific tricks apply and you need a sparse table or segment tree; see segment trees and Fenwick trees.

Problems That Use the Same Monotonic Deque

The deque becomes much more powerful once you see it as "a sliding-window max or min in amortised O(1)". It often speeds up DP transitions of the form dp[i] = nums[i] + max(dp[j]) for j in the last k positions.

LC 1438 is a nice bridge between this problem and the variable-size windows in LeetCode 76 Minimum Window Substring: you expand and shrink the window as usual, but use a max-deque and a min-deque to check validity in O(1). The broader catalogue is in sliding window problems explained.

Interview Tips for Sliding Window Maximum

A strong 15-minute answer looks like this:

1. Brute force (O(n·k)) in one sentence.
2. Heap idea with lazy deletion, O(n log n), as a stepping stone if you want to show progression.
3. The dominance argument: "If a newer element is at least as large, the older one can never be a maximum again, so I discard it."
4. State the invariant: indices in the window, values strictly decreasing, front is the max.
5. Code with the four steps in order: expire, dominate, push, read.
6. Dry run on the LeetCode example and on a decreasing array.
7. Amortised O(n): each index pushed once and popped at most once.

Frequent mistakes

• Storing values instead of indices, then failing on duplicates or being unable to detect expiry.
• Using if instead of while for the dominate step, leaving smaller elements in the deque and breaking the monotonic property.
• Off-by-one in expiry: the window is [i - k + 1, i], so an index expires when it is <= i - k.
• Recording output before the first window is full (forgetting i >= k - 1).
• Claiming O(n·k) because of the inner loop, or claiming O(1) per step without the amortised qualifier.

Follow-ups to expect

• "Return the minimum instead." Flip the comparison to keep an increasing deque.
• "Max and min at the same time." Two deques.
• "Data arrives as a stream with a time-based window (last 60 seconds) rather than a count." Store (timestamp, value) and expire by timestamp; the dominance logic is unchanged. This is the core of a real-time "max latency in the last minute" metric, a nice link to metrics and monitoring system design.
• "Sliding window median." (LC 480.) The deque no longer works because the median is not monotonic-friendly; use two heaps with lazy deletion or an ordered multiset.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.