Google — Sliding Window Maximum (Monotonic Deque)

Problem (Google Classic)

Given array nums and window size k, return the max of each window as it slides from left to right.

Example:

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

Key Insight — Monotonic Deque

Maintain a deque of indices in decreasing order of their values. The front is always the max of the current window.

Before adding i: pop from back while nums[deque.back] <= nums[i] (useless smaller elements)
After adding: pop from front if index is out of window (deque.front <= i - k)
Deque front = current window max

Solutions

Python

from collections import deque

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

JavaScript

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

Java

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

C++

#include <deque>
#include <vector>
using namespace std;
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() && nums[dq.back()]<=nums[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front()<=i-k) dq.pop_front();
        if (i>=k-1) res.push_back(nums[dq.front()]);
    }
    return res;
}

C

#include <stdlib.h>
int* maxSlidingWindow(int* nums, int n, int k, int* sz) {
    int* dq = malloc(n*sizeof(int)), lo=0, hi=0;
    int* res = malloc((n-k+1)*sizeof(int)); *sz=0;
    for (int i=0; i<n; i++) {
        while (hi>lo && nums[dq[hi-1]]<=nums[i]) hi--;
        dq[hi++]=i;
        if (dq[lo]<=i-k) lo++;
        if (i>=k-1) res[(*sz)++]=nums[dq[lo]];
    }
    free(dq); return res;
}

Complexity

Approach	Time	Space
Monotonic deque	O(n)	O(k)
Naive max	O(nk)	O(1)