Sliding Window Maximum — Monotonic Deque O(n) [LC 239]

Problem Statement#

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

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

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

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

Why This Problem Matters#

LeetCode 239 is a hard problem asked frequently at Amazon, Google, and Microsoft. The naive O(n*k) approach — find the max in each window by brute force — times out at n = 10^5. The O(n) monotonic deque solution is elegant and teaches a fundamental pattern used in Jump Game VI (LC 1696), Shortest Subarray with Sum at Least K (LC 862), and many sliding window optimization problems.

The deque maintains a decreasing order of indices: the front is always the maximum of the current window. Two operations keep it valid: remove indices that have left the window from the front, and remove indices from the back whose values are smaller than the current element (they can never be the maximum of any future window).

The Core Insight#

Monotonic decreasing deque of indices. Maintain a deque where values at those indices are decreasing from front to back. The front of the deque is always the index of the maximum in the current window.

For each new element at index i:

1. Remove from front: if deque[front] <= i - k, it's out of the window — pop front
2. Remove from back: while nums[deque[back]] <= nums[i], pop back — these can never be future maximums
3. Append i to the back
4. When the window is full (i >= k-1), record nums[deque[front]] as the answer

Why remove smaller elements from back? If element at index j < i satisfies nums[j] <= nums[i], then for any window containing both j and i, index i will be in the window as long as j is (since i comes later). Index j can never be the maximum of any window that hasn't already ended — it's dominated by i. Remove it.

Visual Dry Run#

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

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

Solution (Optimal)#

from collections import deque
 
class Solution:
    def maxSlidingWindow(self, nums, k):
        dq = deque()   # stores indices, decreasing by value
        result = []
        for i in range(len(nums)):
            # Remove indices outside the window
            while dq and dq[0] <= i - k:
                dq.popleft()
            # Remove indices whose values are <= current (they are dominated)
            while dq and nums[dq[-1]] <= nums[i]:
                dq.pop()
            dq.append(i)
            # Add to result once the first full window is complete
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result

var maxSlidingWindow = function(nums, k) {
    const dq = [];
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        while (dq.length > 0 && dq[0] <= i - k) dq.shift();
        while (dq.length > 0 && nums[dq.at(-1)] <= nums[i]) dq.pop();
        dq.push(i);
        if (i >= k - 1) result.push(nums[dq[0]]);
    }
    return result;
};

Time: O(n) — each index pushed and popped at most once Space: O(k) — deque holds at most k indices

Common Mistakes#

• Storing values instead of indices in the deque — need indices to check if elements are still in the window
• Using < instead of <= when removing elements from the back — equal elements should also be removed (the later one dominates for future windows)
• Checking window full condition as i >= k instead of i >= k - 1 — off by one
• Not checking deque is non-empty before peeking at front — causes index errors
• Using a sorted structure like a heap — O(n log k) which is suboptimal vs O(n) deque

Interview Tips#

• State two operations clearly: "remove expired indices from front, remove smaller elements from back"
• Explain why smaller elements in the back are useless: "they are dominated by the current element for all future windows"
• Show that each element is enqueued/dequeued at most once — O(n) amortized total
• Store indices not values — you need indices for the out-of-window expiry check
• Contrast with heap solution: "max-heap gives O(n log k) but deque achieves O(n) — the same improvement as switching from sorted insertion to amortized deque"

Follow-up Questions#

• How would you find the minimum of each sliding window? (Use monotonic increasing deque — pop from back when current is smaller)
• How does this apply to Jump Game VI (LC 1696)? (dp[i] = nums[i] + max(dp[j]) for j in window — use sliding window max on dp values)
• What is the O(n log k) heap solution? (Min-heap or max-heap of (value, index) pairs; remove outdated indices lazily)
• What if k equals n? (Deque gives the global maximum — same algorithm, result has one element)
• Can you handle duplicate values? (Yes — using <= when removing from back handles ties correctly)

Key Takeaways#

• LeetCode 239 is asked at Amazon, Google, and Microsoft — monotonic deque achieves O(n) vs O(n*k) brute force
• Maintain a monotonic decreasing deque of indices: front is always the current window's maximum
• Remove from front: expired indices (deque[front] <= i - k)
• Remove from back: dominated indices (nums[deque[back]] <= nums[i]) — they can never be future maximums
• Each index is pushed once and popped at most once — O(n) total work, O(k) space
• Store indices not values — needed for the expiry check
• This deque pattern solves Jump Game VI, Shortest Subarray with Sum at Least K, and many DP optimization problems