Sliding Window Maximum — Monotonic Deque Pattern

Sliding Window Maximum asks for the max of every length-k window. A naive scan is O(n*k); a heap gets to O(n log k). The slick answer is a monotonic deque that runs in O(n) total.

The Problem

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

Example:

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

Intuition

For each window, the brute force scans all k elements — O(n*k), fine for small inputs but TLE for large ones.

The smarter idea is to maintain a deque of indices such that the values they point to are strictly decreasing. The front always holds the index of the current window’s max. Two operations follow naturally from this invariant. First, evict the front when it falls outside the window. Second, pop the back while it is smaller than the incoming value, because it can never be the max while the new value is present and newer. Each index is pushed and popped at most once, so total work is O(n).

Explanation with Example

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

• i=0: deque becomes [0].
• i=1: 3 > 1, pop 0, push 1. Deque [1].
• i=2: -1 < 3, push 2. Deque [1,2]. Window full, record nums[1]=3.
• i=3: -3 < -1, push 3. Front index 1 still in window. Record 3.
• i=4: 5 evicts back entries; index 1 also falls out of window. Deque [4]. Record 5.
• Continue: results [3,3,5,5,6,7].

nums    1   3  -1  -3   5   3   6   7
      [1  3  -1]                       max = 3
          [3  -1  -3]                  max = 3
             [-1  -3   5]              max = 5
                 [-3   5   3]          max = 5
                      [5   3   6]      max = 6
                          [3   6   7]  max = 7

deque after i=4: front -> [5]   (3 and -1 popped)

Code

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    res = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
            dq.offerLast(i);
            if (i >= k - 1) res[idx++] = nums[dq.peekFirst()];
        }
        return res;
    }
}

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> res;
        for (int i = 0; i < (int)nums.size(); ++i) {
            while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
            while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
            dq.push_back(i);
            if (i >= k - 1) res.push_back(nums[dq.front()]);
        }
        return res;
    }
};

Edge Cases

• k == 1: result equals nums.
• k == len(nums): one window, returns the global max.
• All equal values: the deque holds one or many equal entries depending on < vs <= policy; using strict < keeps duplicates, both work.
• Negative numbers and zeros mix freely; comparisons handle them.

Complexity Analysis

• Brute force: O(n*k) time, O(1) extra.
• Heap solution: O(n log k) time, O(k) space (needs lazy deletion).
• Monotonic deque: O(n) time, O(k) space.

The deque is optimal in both axes.

How to Explain It in an Interview

State the invariant first: the deque stores indices in increasing order of position, with strictly decreasing values. From that, two operations follow naturally — evict the front when it falls outside the window, and pop the back while it is smaller than the incoming value. Walk through the first few iterations to demonstrate. Highlight amortized O(n) because each index enters and exits the deque at most once.

Related Problems

• Longest Substring Without Repeating Characters (sliding window)
• Minimum Window Substring
• Sliding Window Median (heap + lazy deletion)
• Shortest Subarray with Sum at Least K (deque on prefix sums)

Wrap up

Once you see the eviction rule, you will spot the pattern everywhere: shortest subarray with sum constraints, stock spans, next greater element. Memorize the template and adapt the comparison.