Sliding Window Maximum [Hard] — Monotonic Deque

Problem Statement

Given array nums and integer k, find the max in every window of size k.

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

Intuition

Maintain a monotonic decreasing deque of indices. The front is always the current window's max. Remove from back if smaller than current element (they can never be the max). Remove from front if outside window.

Solutions

C++

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> res;
    for (int i=0; i<nums.size(); i++) {
        while (!dq.empty() && dq.front()<i-k+1) 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;
}

Java

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

JavaScript

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

Python

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()  # stores indices, monotone decreasing by value
    res = []
    for i, val in enumerate(nums):
        # Remove out-of-window indices
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Remove smaller elements
        while dq and nums[dq[-1]] < val:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

Complexity

Time: O(n) — each element added/removed from deque at most once
Space: O(k)