Sliding Window Maximum (LC 239) — Monotonic Deque Deep Dive

Problem Statement#

LeetCode 239 — Sliding Window Maximum (Hard)

You are given an integer array nums and an integer k. There is a sliding window of size k moving from the leftmost position to the rightmost position. Each step the window moves one position to the right. Return an array of the maximums of each window position.

Constraints:

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

Example 1:

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

Example 2:

Input:  nums = [1], k = 1
Output: [1]
Explanation: Only one window, one element.

Example 3:

Input:  nums = [9, 11], k = 2
Output: [11]
Explanation: Single window [9, 11], max = 11.

Why This Problem Matters#

LC 239 is one of the most frequently cited "hard" problems in FAANG loops at Google, Amazon, and Microsoft. The brute-force O(nk) approach is trivially obvious — slide a window and scan for the max each time. The challenge is reducing that to O(n). This is where the monotonic deque shines: it maintains a decreasing sequence of indices so that the front always holds the current window's maximum in O(1).

Beyond interviews, this pattern underpins real systems: network traffic monitoring (max bandwidth in a rolling window), financial systems (rolling high/low prices), game engines (visibility checks), and time-series anomaly detection. Mastering the monotonic deque unlocks an entire family of O(n) range-query problems that would otherwise require O(n log n) segment trees.

The Core Insight#

For any window, an element nums[i] can never be the answer if there exists an element nums[j] with j > i and nums[j] >= nums[i], because both are in the window at the same time and nums[j] will win. This means we can discard nums[i] permanently. This "discard dominated elements" rule leads directly to a monotonic decreasing deque of indices.

The deque stores indices (not values) in decreasing order of their corresponding values. Three invariants are maintained at every step i:

1. Out-of-window cleanup: Pop the front index if it is no longer within [i-k+1, i].
2. Monotone maintenance: Pop the back index while nums[back] <= nums[i] — the current element dominates them.
3. Record maximum: After both pops, push i. If the window is full (i >= k-1), nums[deque.front()] is the answer.

Each index is pushed and popped at most once, giving amortized O(1) per element and O(n) overall.

Visual Dry Run#

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

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

Note: at i=3, index 0 would be evicted (outside window [1..3]) but it was already popped. At i=4, index 1 is also outside window [2..4] and gets cleaned from the front before value comparison.

Common Mistakes#

1. Storing values instead of indices. If you store values in the deque, you cannot check whether the front element has slid out of the window. Always store indices.

2. Wrong order of cleanup. You must remove out-of-window indices from the front before recording the answer. Failing to do this returns stale maximums.

3. Using < instead of <= when popping the back. If you use strict <, equal elements remain in the deque unnecessarily. Use <= so that older equal elements are replaced by newer ones (which have a later expiry). Both technically work, but <= keeps the deque lean.

4. Off-by-one on window-full check. The first full window exists when i == k-1. If you check i > k-1 you miss the first output.

5. Confusing deque front and back. Front holds the oldest (largest) index, back holds the newest. The maximum is always at the front. Mixing these up produces wrong answers.

6. Not handling k = 1 separately. With k=1, every element is its own window max. The algorithm handles this correctly, but forgetting to test this edge case is a common interview pitfall.

7. Using a heap (priority queue) instead of a deque. A max-heap gives O(n log k) time, which is correct but not optimal. Interviewers often probe whether you can do O(n).

Solutions#

Python#

from collections import deque
 
def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()   # stores indices; values are monotone decreasing
    result = []    # output: one max per window position
 
    for i in range(len(nums)):
        # Step 1: evict indices that have slid out of the window
        # front of deque holds the oldest index; if it's too old, remove it
        while dq and dq[0] < i - k + 1:
            dq.popleft()
 
        # Step 2: maintain monotone decreasing property
        # any index at the back with a smaller or equal value is dominated
        # by nums[i] and can never be a future maximum
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
 
        # Step 3: add current index to the back
        dq.append(i)
 
        # Step 4: once the first full window is formed, record the max
        # front of deque always holds the index of the window maximum
        if i >= k - 1:
            result.append(nums[dq[0]])
 
    return result

JavaScript#

var maxSlidingWindow = function(nums, k) {
    const dq = [];      // monotonic deque storing indices
    const result = [];  // output array
 
    for (let i = 0; i < nums.length; i++) {
        // Step 1: remove indices no longer in the current window [i-k+1, i]
        // the front of the deque holds the oldest index
        while (dq.length > 0 && dq[0] < i - k + 1) {
            dq.shift();   // evict expired index from front
        }
 
        // Step 2: remove indices from the back whose values are dominated
        // nums[i] is >= them, so they can never be a window maximum
        while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[i]) {
            dq.pop();     // discard dominated index from back
        }
 
        // Step 3: push current index onto the back
        dq.push(i);
 
        // Step 4: the first full window completes at index k-1
        // from that point on, the front of the deque is the window max
        if (i >= k - 1) {
            result.push(nums[dq[0]]);
        }
    }
 
    return result;
};

Complexity Analysis#

The deque holds at most k elements at any time, giving O(k) space. Total time is O(n) because each of the n elements is enqueued and dequeued at most once across the entire traversal.

Follow-up Questions#

1. What if k changes dynamically? With a static deque you'd need to rebuild. A segment tree or sparse table supports arbitrary range-max queries in O(1) after O(n log n) preprocessing — better for this case.

2. Sliding window minimum? Flip the comparison: maintain a monotone increasing deque instead of decreasing. The front always holds the minimum.

3. What if you need both min and max simultaneously? Maintain two separate deques: one increasing (min) and one decreasing (max). Both run in O(n) total.

4. Can you solve this problem with a sorted container? Yes — a sorted multiset (C++ multiset) lets you insert and erase in O(log k) and query max in O(1). Total O(n log k). Correct but slower than the deque.

5. How would you parallelize this for a distributed stream? Partition the stream into chunks with overlap of k-1 elements at boundaries. Process each chunk independently with the deque algorithm, then merge boundary windows.

This Pattern Solves#

• LC 239 — Sliding Window Maximum (this problem)
• LC 862 — Shortest Subarray with Sum at Least K (monotonic deque on prefix sums)
• LC 1438 — Longest Continuous Subarray With Absolute Diff <= Limit (two deques)
• LC 2398 — Maximum Number of Robots Within Budget (deque for running max)
• LC 918 — Maximum Sum Circular Subarray (Kadane + deque variant)

Key Takeaway#

The monotonic deque is the right tool whenever you need a running maximum or minimum over a sliding window in O(n) time. Store indices (not values) so you can evict expired elements. The invariant is simple: maintain a decreasing sequence so the front is always the answer. Once you internalize this pattern, you can solve an entire class of hard sliding-window problems that would otherwise require O(n log n) range-query structures.

Key Takeaways#

• LC 239 (Sliding Window Maximum) is a top hard sliding-window problem asked by Google, Amazon, and Microsoft — it appears in both phone screens and onsites.
• Maintain a monotone decreasing deque of indices: pop from the back any index whose value is <= nums[right] before pushing right — this keeps the front always the current window maximum.
• Store indices (not values) in the deque so you can evict expired elements: pop from the front when deque[0] <= right - k.
• Begin recording results only when right >= k - 1 — the first full window is complete at that point.
• Time O(n), space O(k) — each element is pushed and popped from the deque at most once, giving amortized O(1) per element.
• For sliding window minimum, maintain a monotone increasing deque instead — one character change in the comparison.
• This monotonic deque pattern generalizes to LC 862 (shortest subarray sum at least k), LC 1438 (absolute diff limit), and LC 1499 (max value of equation) — the deque on prefix sums is the same structure applied to different objectives.