Sliding Window Maximum

hard sliding window monotonic deque

Problem

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Inputnums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

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

Maintain a deque of indices whose values are decreasing from front to back.

nums (comma-separated)

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    out = []
    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:
            out.append(nums[dq[0]])
    return out

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

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();
        int[] out = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; 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) out[i - k + 1] = nums[dq.peekFirst()];
        }
        return out;
    }
}

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> out;
    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) out.push_back(nums[dq.front()]);
    }
    return out;
}

Explanation

We need the maximum of every length-k window. Re-scanning all k numbers each time is wasteful. The fast trick is a monotonic deque — a double-ended queue of indices whose values are kept in decreasing order, so the front always holds the index of the current window's maximum.

As we walk index i, we first drop indices that have slid out of the window: if dq[0] <= i - k, the front is too old, so we pop it from the left.

Next we keep the deque decreasing: while the value at the back, nums[dq[-1]], is smaller than the new nums[i], we pop it from the back. Those smaller numbers can never be a maximum while the bigger newcomer is around. Then we append i.

Once i reaches k - 1, every window is complete, so we read off nums[dq[0]] as that window's maximum.

Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. Each index enters and leaves the deque at most once, so the whole thing runs in a single linear pass and produces [3, 3, 5, 5, 6, 7].

Time: O(n) Space: O(k)