Sliding Window Maximum [Hard] — Monotonic Deque Explained (LeetCode 239)

Problem Statement

Given an integer array nums and an integer k, there is a sliding window of size k which moves from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position, return the maximum of all elements in every window.

You must solve it in O(n log n) or better.

Examples:

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

Window [1,3,-1]  → max = 3
Window [3,-1,-3] → max = 3
Window [-1,-3,5] → max = 5
Window [-3,5,3]  → max = 5
Window [5,3,6]   → max = 6
Window [3,6,7]   → max = 7

Input:  nums = [1], k = 1
Output: [1]

Constraints: 1 <= k <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4

• Why This Problem Matters
• Naive Approach — Brute Force O(n·k)
• The Monotonic Deque Insight
• The Deque Invariant
• Rule 1 — Remove from the BACK (Useless Elements)
• Rule 2 — Remove from the FRONT (Expired Elements)
• Rule 3 — Record the Result
• Visual Dry Run
• Common Mistakes
• Solutions
• Brute Force — O(n·k) Time, O(1) Extra Space
• Optimal — Monotonic Deque, O(n) Time, O(k) Space
• Complexity Analysis
• Brute Force
• Monotonic Deque
• Follow-up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 239 is the canonical Hard on monotonic data structures and one of the most frequently reported interview questions at Amazon, Google, and Microsoft — not because the code is long, but because the key insight is genuinely non-obvious.

Almost every other sliding window problem (Minimum Size Subarray Sum, Longest Substring Without Repeating Characters, etc.) either shrinks the window dynamically or counts elements. This one is different: the window size is fixed and you need the running maximum of each window. That combination destroys the standard two-pointer template and forces you to think differently.

The brute-force is obvious. The correct O(n) solution requires understanding a data structure — the monotonic deque — that most people have never seen before an interview. That gap is exactly what interviewers at these companies are probing for.

Beyond the single problem, the monotonic deque pattern is a gateway to an entire family of hard DP optimizations. Once you understand it here, problems like Jump Game VI (LC 1696) and Constrained Subsequence Sum (LC 1425) become approachable because they reduce to the same underlying operation: "find the maximum over a sliding window of size k."

Interview frequency: This exact problem or a direct variant is reported in roughly 1 in 4 hard-level system-design or algorithmic rounds at Amazon and Google, particularly for SDE-2/SDE-3 roles. A correct O(n) solution with a clear explanation of why the deque maintains the invariant is usually sufficient to advance to the next round.

Naive Approach — Brute Force O(n·k)

The simplest approach is to slide the window one step at a time and scan all k elements in each window to find the maximum.

for each starting index i from 0 to n-k:
    scan nums[i..i+k-1] and find the max
    append max to result

There are (n - k + 1) windows. Each window takes O(k) to scan. Total: O(n·k).

For the maximum constraints (n = 10^5, k = 10^5), this is up to 10^10 operations — guaranteed TLE.

A heap (priority queue) improves this to O(n log k) — better, but it still fails to hit the O(n) requirement. The heap approach also has a subtle correctness issue: you cannot efficiently determine whether the heap's maximum is still inside the current window without marking deleted elements (lazy deletion), which complicates the implementation significantly.

The problem demands something smarter: a way to maintain the running maximum as the window slides without re-scanning elements we have already seen.

The Monotonic Deque Insight

Here is the key observation that makes O(n) possible:

An element can never be the maximum of any future window if there is a larger element to its right that is still within the window.

Think about it concretely. Suppose you are at index i and you see a new element nums[i]. Any element nums[j] (where j < i) that is smaller than nums[i] is now permanently useless. Here is why:

• Every future window that contains index j also contains index i (because i > j and the window slides right).
• nums[i] > nums[j], so nums[j] can never be the maximum of any window that contains both of them.
• Eventually, j will slide out of the window before i does, so there is no future window where j is present but i is not.

This means we do not need to store every element in the current window. We only need to store candidates — elements that could still be the maximum of some future window. Every element that is smaller than the newest element has already been disqualified. We can throw it away immediately.

A deque (double-ended queue) lets us efficiently add to one end and remove from either end, which is exactly what this pattern requires.

The Deque Invariant

The monotonic deque maintains one strict invariant at all times:

Elements in the deque are always in strictly decreasing order of their values, from front to back. The front of the deque always holds the index of the current window's maximum.

To maintain this invariant, two rules govern every operation:

Rule 1 — Remove from the BACK (Useless Elements)

Before adding a new element nums[i] to the deque, pop all indices from the back whose corresponding values are less than or equal to nums[i]. Those elements are now permanently dominated and can never be a future maximum.

while deque is not empty AND nums[deque.back()] <= nums[i]:
    deque.pop_back()
deque.push_back(i)

Note: some implementations use strict < here. Using <= is slightly more correct because equal elements at the back are also dominated by the newer one — the newer one will outlive the older one in the window.

Rule 2 — Remove from the FRONT (Expired Elements)

The front of the deque is the current maximum, but only if it is still inside the window. After adding the new element, check whether the front index has slid out of the window:

while deque is not empty AND deque.front() < i - k + 1:
    deque.pop_front()

The boundary i - k + 1 is the leftmost valid index of the current window. Any index strictly less than this is expired.

Rule 3 — Record the Result

Once the window is fully formed (i.e., i >= k - 1), the front of the deque is the answer for the current window:

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

Visual Dry Run

Let us trace nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 step by step. The deque stores indices (values shown in brackets for clarity).

Index: 0  1   2   3   4  5  6  7
Value: 1  3  -1  -3   5  3  6  7

i = 0, val = 1

• Deque is empty — nothing to pop from back.
• Push 0. Deque: [0(1)]
• Window not yet full (i < 2). No output.

i = 1, val = 3

• Back of deque: index 0, value 1. Is 1 <= 3? Yes → pop.
• Deque empty → push 1. Deque: [1(3)]
• Window not yet full. No output.

i = 2, val = -1

• Back of deque: index 1, value 3. Is 3 <= -1? No → keep.
• Push 2. Deque: [1(3), 2(-1)]
• i = 2 >= k-1 = 2. Front is index 1, value 3.
• Output: [3]

i = 3, val = -3

• Back of deque: index 2, value -1. Is -1 <= -3? No → keep.
• Push 3. Deque: [1(3), 2(-1), 3(-3)]
• Front is index 1. Is 1 < 3-3+1 = 1? No (not strictly less) → keep.
• Front value = 3.
• Output: [3, 3]

i = 4, val = 5

• Back of deque: index 3, value -3. Is -3 <= 5? Yes → pop.
• Back of deque: index 2, value -1. Is -1 <= 5? Yes → pop.
• Back of deque: index 1, value 3. Is 3 <= 5? Yes → pop.
• Deque empty → push 4. Deque: [4(5)]
• Front is index 4. Is 4 < 4-3+1 = 2? No → keep.
• Front value = 5.
• Output: [3, 3, 5]

i = 5, val = 3

• Back of deque: index 4, value 5. Is 5 <= 3? No → keep.
• Push 5. Deque: [4(5), 5(3)]
• Front is index 4. Is 4 < 5-3+1 = 3? No → keep.
• Front value = 5.
• Output: [3, 3, 5, 5]

i = 6, val = 6

• Back of deque: index 5, value 3. Is 3 <= 6? Yes → pop.
• Back of deque: index 4, value 5. Is 5 <= 6? Yes → pop.
• Deque empty → push 6. Deque: [6(6)]
• Front is index 6. Is 6 < 6-3+1 = 4? No → keep.
• Front value = 6.
• Output: [3, 3, 5, 5, 6]

i = 7, val = 7

• Back of deque: index 6, value 6. Is 6 <= 7? Yes → pop.
• Deque empty → push 7. Deque: [7(7)]
• Front is index 7. Is 7 < 7-3+1 = 5? No → keep.
• Front value = 7.
• Output: [3, 3, 5, 5, 6, 7] ✓

Common Mistakes

These five bugs appear constantly in interview implementations and code reviews:

Mistake 1 — Storing values instead of indices in the deque. This is the single most common error. If you store values, you cannot check whether the front element is still inside the window — you have no positional information. Always store indices and look up nums[index] when you need values.

Mistake 2 — Wrong order of operations: checking front before adding to back. The correct order is: (1) remove expired front, (2) remove dominated back elements, (3) push new index, (4) read front as result. Doing step 4 before step 3 means you are reading the maximum before incorporating the new element. Doing step 1 after step 3 can cause you to read an index that has already been pushed but should have been evicted.

Mistake 3 — Wrong boundary condition: < vs <= when popping the front. The condition to evict the front should be deque.front() < i - k + 1 (the front index is strictly less than the leftmost valid index). Using <= would incorrectly evict an element that is exactly at the window boundary and is still valid.

Mistake 4 — Wrong removal condition at the back: < vs <=. When popping dominated elements from the back, using < (strict) means equal elements are kept. This is not a correctness bug for the maximum itself, but it leaves stale duplicate entries in the deque that waste space and time. Using <= is the cleaner and more standard choice.

Mistake 5 — Recording output before the window is fully formed. The first valid window is at index k - 1. Outputting results starting at index 0 produces garbage. Guard your output with if i >= k - 1.

Solutions

Brute Force — O(n·k) Time, O(1) Extra Space

Python:

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    n = len(nums)
    result = []

    for i in range(n - k + 1):
        # Scan every element in the current window
        window_max = nums[i]
        for j in range(i + 1, i + k):
            if nums[j] > window_max:
                window_max = nums[j]
        result.append(window_max)

    return result

JavaScript:

var maxSlidingWindow = function(nums, k) {
    const result = [];

    for (let i = 0; i <= nums.length - k; i++) {
        // Scan every element in the current window
        let windowMax = nums[i];
        for (let j = i + 1; j < i + k; j++) {
            if (nums[j] > windowMax) windowMax = nums[j];
        }
        result.push(windowMax);
    }

    return result;
};

Optimal — Monotonic Deque, O(n) Time, O(k) Space

Python:

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    # deque stores INDICES, not values
    # Elements are maintained in decreasing order of their values
    dq = deque()
    result = []

    for i, val in enumerate(nums):
        # Step 1: Evict expired indices from the front
        # The leftmost valid index for window ending at i is (i - k + 1)
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Step 2: Remove dominated elements from the back
        # Any index whose value is <= val can never be a future max
        while dq and nums[dq[-1]] <= val:
            dq.pop()

        # Step 3: Add current index
        dq.append(i)

        # Step 4: Record result once the first full window is formed
        if i >= k - 1:
            result.append(nums[dq[0]])  # front is always the current max

    return result

JavaScript:

var maxSlidingWindow = function(nums, k) {
    // dq stores INDICES, not values
    // Front = current window max (by index); back = smallest in deque
    const dq = [];
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        // Step 1: Evict indices that have slid out of the window
        while (dq.length && dq[0] < i - k + 1) {
            dq.shift(); // O(n) in JS arrays — acceptable for interview; use a real deque for production
        }

        // Step 2: Remove indices whose values are dominated by nums[i]
        while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) {
            dq.pop();
        }

        // Step 3: Add current index
        dq.push(i);

        // Step 4: Record result once window is fully formed
        if (i >= k - 1) {
            result.push(nums[dq[0]]); // front is always the window maximum
        }
    }

    return result;
};

Production note (JavaScript): Array.shift() in JavaScript is O(n) because it shifts all remaining elements. For truly optimal performance, implement a circular buffer deque or use a doubly-linked list. For an interview setting, this is accepted.

Complexity Analysis

Brute Force

• Time: O(n·k) — (n - k + 1) windows, O(k) scan per window.
• Space: O(1) extra (output array not counted).

Monotonic Deque

• Time: O(n) amortized.

  Here is the proof sketch: every index is pushed into the deque exactly once and popped from the deque at most once (either from the back when dominated, or from the front when expired). The total number of push + pop operations across the entire run is therefore bounded by 2n. No index is ever processed more than twice. This gives O(n) total regardless of k.

• Space: O(k) — the deque holds at most k indices at any moment (at most one per window position).

The heap approach sits in between: O(n log k) time with O(k) space. It is correct but slower and more complex to implement cleanly in an interview.

Follow-up Questions

Q1: Sliding Window Minimum. Identical structure — flip the comparison. Maintain a monotonically increasing deque instead of decreasing. The front is always the current minimum. Every rule is mirrored: pop from the back when the back value is >= the new element.

Q2: Maximum of all subarrays of size k where elements can repeat. No change needed — the <= back-pop condition already handles duplicates correctly.

Q3: Jump Game VI (LeetCode 1696). You have an array nums and can jump 1 to k steps forward. Maximize the sum of visited indices. The DP recurrence is dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]). That max over a sliding window of size k is exactly the monotonic deque pattern applied to the DP array instead of the input array. Reduces from O(n·k) to O(n).

Q4: Constrained Subsequence Sum (LeetCode 1425). Choose a non-empty subsequence where consecutive chosen elements are at most k indices apart. Maximize the sum. Again, the optimal DP recurrence requires max(dp[i-k..i-1]) at every step — same monotonic deque optimization, same O(n) result.

Q5: Shortest Subarray with Sum at Least K (LeetCode 862). Uses a monotonic deque on prefix sums to find the shortest subarray. A different flavor — here you are tracking a monotone increasing prefix sum deque — but the same conceptual tool.

This Pattern Solves

Whenever a dynamic programming recurrence or sliding window query has the form:

result[i] = f(nums[i], max(or min) over window [i-k, i-1])

a monotonic deque reduces the naive O(n·k) to O(n). Problems in this family include:

Key Takeaway

The monotonic deque works because it discards elements that are provably useless: any element that is smaller than a newer element to its right can never be a future window maximum, so it is removed immediately. This "lazy pruning" means each element is touched at most twice across the entire array, giving true O(n) time regardless of window size.

Once you internalize the invariant — the deque is always decreasing in value, front is always the current window max — the implementation follows mechanically from two rules: pop the back when dominated, pop the front when expired. Master this pattern here, and a whole family of hard DP optimization problems becomes tractable at first sight.