239. Sliding Window Maximum

Quick Identifier

Topic: sliding-window
Pattern: Monotonic Deque (Window Maximum)
Hint: Maintain a decreasing deque of indices; the front always holds the maximum for the current window of size k.
Difficulty: Hard
Companies: Amazon, Google, Bloomberg, Microsoft, Adobe
LeetCode: 239

Quick Sights

Time Complexity: O(n) – each element is pushed and popped at most once from the deque.
Space Complexity: O(k) – the deque stores at most k indices.
Core Mechanism: For each index i:
1. Remove indices that are out of the window (i - k).
2. Pop from the back while the current value is greater than or equal to values at those indices (they become useless).
3. Push the current index.
4. The front of the deque is the index of the maximum for the current window.

Think of the deque as a line of athletes waiting to run a race. The athlete at the front is always the strongest (largest value) because any weaker athlete behind a stronger one would never win while the stronger stays in the window. When an athlete leaves the race (index out of range) we drop them from the front. When a new, stronger athlete arrives, we discard all weaker athletes from the back – they can never become the front again.

Diagram

Loading diagram…

Study Pattern (SDE3+)

0‑3 min: Identify the monotonic‑deque pattern, compare it to the naive O(k) scanning approach, and highlight amortized O(1) per element.
Implementation pass: Emphasise storing indices, not values, so we can efficiently drop expired elements.
5 min extension: Discuss alternative data structures (max‑heap) and why the deque is superior in an interview (linear time, simpler code).

Approaches

Brute force – scan each window of size k, O(n·k).
Heap – maintain a max‑heap of window elements, O(n·log k).
Optimal – monotonic deque, O(n) time, O(k) space. (Always pick this)

Optimal Solution

Go

func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 || k == 0 {
        return []int{}
    }
    deque := make([]int, 0) // stores indices
    result := make([]int, 0, len(nums)-k+1)
    for i := 0; i < len(nums); i++ {
        // remove indices out of the current window
        if len(deque) > 0 && deque[0] < i-k+1 {
            deque = deque[1:]
        }
        // remove smaller values from the back
        for len(deque) > 0 && nums[deque[len(deque)-1]] <= nums[i] {
            deque = deque[:len(deque)-1]
        }
        deque = append(deque, i)
        // record max when we have a full window
        if i >= k-1 {
            result = append(result, nums[deque[0]])
        }
    }
    return result
}

JavaScript

function maxSlidingWindow(nums, k) {
    if (!nums.length || k === 0) return [];
    const deque = []; // stores indices
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        // Remove indices out of the current window
        if (deque.length && deque[0] < i - k + 1) {
            deque.shift(); // O(n) in JS arrays but acceptable for interview demos
        }
        // Remove smaller values from the back
        while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }
        deque.push(i);
        // Record max when window is full
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }
    return result;
}

Walkthrough

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

After processing indices 0‑2, deque = [1] (value 3) → output 3.
Slide window: index 3 (-3) does not affect deque front; output remains 3.
Continue similarly, yielding result [3,3,5,5,6,7].

Edge Cases

k == 1 → output is a copy of nums.
k == len(nums) → output a single element = global max.
All decreasing numbers – deque will contain all indices of the current window.

Pitfalls

Storing values instead of indices; you lose the ability to know when an element exits the window.
Using < instead of <= when popping from the back; you may keep duplicates and waste space.
Forgetting to record the result only after the first full window (i >= k-1).

Mind‑Map Tags

#sliding-window #monotonic-deque #window-maximum #hard #optimal