Sliding Window Maximum — Monotonic Deque for O(n) Solution

Problem Statement#

You are given an array of integers nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. Return an array of the maximum value in each window position.

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]
Explanation:
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]

Input:  nums = [9,11], k = 2
Output: [11]

Why This Problem Matters#

LC 239 is one of the hardest and most important deque problems in competitive programming and FAANG interviews. The monotonic deque technique it introduces is the exact same technique used in:

• Shortest Subarray with Sum At Least K (LC 862) — same deque, prefix sums instead of values.
• Jump Game VI (LC 1696) — same deque, DP transitions instead of window max.
• Max Sliding Window in Streaming Systems — rate limiters, analytics dashboards.
• Constrained Subsequence Sum (LC 1425) — deque DP.

The problem teaches: when you need the maximum (or minimum) over a sliding window efficiently, a monotonic deque beats the naive O(k) per window approach by maintaining only "useful" candidates.

Companies: Google, Amazon, Microsoft, Adobe. This is a hard-level problem but the technique is worth mastering because it appears in medium-hard DP problems that would otherwise seem unapproachable.

The Core Insight#

Naive approach: For each window position, scan k elements to find the maximum. O(n*k) time — too slow for n = 10^5.

Monotonic deque approach: Maintain a deque of indices in monotonically decreasing order of values. At any point, the front of the deque is the index of the maximum element in the current window.

Two invariants maintained:

1. Monotone decreasing: before pushing index i, pop from the back all indices j where nums[j] <= nums[i]. Element at index j is useless — nums[i] is at least as large and newer (will outlast j in the window).
2. Window validity: before reading the front, pop from the front any index j where j <= i - k (it has slid out of the window).

Why does this work? The deque stores only "useful" candidates: those that could be the maximum for a future window. A smaller element that arrives after a larger one can never be the maximum while the larger one is still in the window — so we eliminate it immediately.

Visual Dry Run#

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

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

Solution (Optimal)#

# Python — monotonic decreasing deque, O(n) time and O(k) space
from collections import deque
 
def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()  # stores INDICES; front = index of current window maximum
    result = []
 
    for i in range(len(nums)):
        # Step 1: Evict indices that have fallen outside the window from the front
        while dq and dq[0] <= i - k:
            dq.popleft()
 
        # Step 2: Remove indices from the back whose values are <= nums[i]
        # They can never be the maximum while nums[i] is in the window
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
 
        # Step 3: Push current index
        dq.append(i)
 
        # Step 4: Record the maximum (front of deque) once the window is full
        if i >= k - 1:
            result.append(nums[dq[0]])
 
    return result

// JavaScript — monotonic decreasing deque, O(n) time and O(k) space
function maxSlidingWindow(nums, k) {
    const dq = [];      // array used as deque: push to back, shift from front
    const result = [];
 
    for (let i = 0; i < nums.length; i++) {
        // Evict out-of-window indices from the front
        while (dq.length > 0 && dq[0] <= i - k) {
            dq.shift();
        }
 
        // Remove smaller-or-equal elements from the back
        while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[i]) {
            dq.pop();
        }
 
        dq.push(i);
 
        // Record maximum once window is full
        if (i >= k - 1) {
            result.push(nums[dq[0]]);
        }
    }
 
    return result;
}

Note for JavaScript: Using an array with shift() is O(n) per eviction. For large inputs, use a proper deque (circular buffer or linked list) to achieve true O(1) front operations. For LeetCode constraints, the array-based approach is accepted.

Complexity:

Common Mistakes#

1. Storing values instead of indices. You need indices to check whether a candidate has left the window (j <= i - k). Storing values makes window expiry impossible to detect.

2. Wrong order of operations. Always: (1) evict from front, (2) remove smaller from back, (3) push current, (4) record result. Changing the order breaks the invariant.

3. Using < instead of <= when evicting from the back. If you use strict less-than, you keep indices of equal values unnecessarily. For maximum, both < and <= give correct results, but <= is cleaner — equal elements are never "more useful" than the newer equal element.

4. Window expiry check off-by-one. The condition is dq[0] <= i - k (note: <=, not <). An index j is outside the window of size k ending at i when j < i - k + 1, equivalently j <= i - k.

5. Not waiting until i >= k - 1 to record results. The window is not full until i = k - 1. Recording before that gives incorrect early results.

Interview Tips#

• Explain the "useless element" insight: "If element j is smaller than element i, and i comes after j, then j can never be the maximum of any future window — because i is in that window and is larger. So we eliminate j immediately."
• State the two-pointer eviction clearly: "Front eviction handles window expiry (left boundary). Back eviction handles the monotone invariant (useless smaller elements)."
• Time complexity argument: "Each index is pushed once and popped at most once from either end — at most 2n deque operations total → O(n)."

Follow-up Questions#

1. Sliding Window Minimum. Same approach with monotonic increasing deque (pop from back when nums[dq[-1]] >= nums[i]).
2. Shortest Subarray with Sum at Least K (LC 862) — monotonic deque on prefix sums; same front/back eviction pattern.
3. Jump Game VI (LC 1696) — monotonic deque for DP max over the last k elements.
4. Constrained Subsequence Sum (LC 1425) — same deque DP pattern.
5. Sliding window median. Two heaps (max-heap + min-heap) rebalanced as the window slides; O(n log k) per operation.

Key Takeaways#

• A monotonic decreasing deque maintains the maximum of a sliding window: front = current max, back = candidates for future maxima.
• Store indices in the deque, not values — you need indices to enforce the window boundary.
• Two eviction rules: (1) front: remove indices that have slid out of the window; (2) back: remove indices whose values are smaller than or equal to the current element (they are useless).
• O(n) total time: each index is pushed and popped at most once across both ends.
• The same monotonic deque pattern solves Shortest Subarray with Sum At Least K (LC 862), Jump Game VI (LC 1696), and Constrained Subsequence Sum (LC 1425).
• In JavaScript, dq.shift() is O(n) — use a proper circular buffer for production or large-scale inputs.