Sliding Window Maximum

Reporting the maximum of every window as it slides is the deque’s signature trick — O(n), not O(n·k).

The problem

You are streaming stock prices, and a trader wants a running "highest price in the last k ticks" line on the chart. Every time a new tick arrives, the window of the last k prices slides forward by one, and you must report the maximum of that window — instantly, for every position.

With thousands of ticks a second and a window of a few hundred, "just look at the window" feels fine until the chart starts stuttering. The window is small, but you are re-scanning it on every single tick, and that re-scanning is where all your time goes.

A first attempt

The direct translation: for each window position, loop over its k elements and take the max.

def max_window_naive(nums, k):
    result = []
    for i in range(len(nums) - k + 1):
        result.append(max(nums[i:i + k]))  # scans k elements
    return result

For an array of length n there are about n windows, and each max costs O(k). That is O(n·k). When k grows with the data, this drifts toward O(n²) — exactly the stutter the trader sees. The waste is obvious once you name it: sliding one step only removes one element and adds one, yet we recompute the whole max from scratch.

The insight

Here is the key observation. Suppose two prices are both still inside the window, and the one on the left is smaller than the one on its right. The left one can never be the answer again: the right one is bigger and will stay in the window at least as long. So the smaller, older value is dead weight — we can throw it away the moment a bigger newer value appears.

If you keep the window's candidates in decreasing order, the front is always the current maximum. Enforcing that order needs a structure where you drop from the back (kill smaller newcomers' victims) and drop from the front (evict values that slid out of the window). Drop from both ends, in O(1) — that is a deque. We store indices so we can tell when a value has left the window.

How it works

We keep a deque of indices whose values are strictly decreasing from front to back.

nums = [1, 3, -1, -3, 5, 3], k = 3

window [1, 3, -1]   deque idx: [1, 2]      -> max nums[1] = 3
window [3, -1, -3]  deque idx: [1, 2, 3]   -> max nums[1] = 3
window [-1, -3, 5]  deque idx: [4]         -> max nums[4] = 5
window [-3, 5, 3]   deque idx: [4, 5]      -> max nums[4] = 5

Slide in the new index

For each new index i, first make room: while the deque's back holds a value smaller than or equal to nums[i], pop it. Those values can never win again, so discard them.

Push the new index

Append i to the back. The deque stays decreasing front-to-back, so its front is the largest candidate so far.

Evict the expired front

If the front index is i - k or older, it has slid out of the window — pop it from the front. At most one eviction per step.

Record the maximum

Once i reaches k - 1, the window is full: nums[deque.front] is this window's maximum. Append it and move on.

Each index is pushed once and popped once, so the total work is linear.

The code

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()          # holds indices, values decreasing
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                 # drop smaller tails
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()             # evict out-of-window front
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = []; // indices, values decreasing
  const result: number[] = [];
  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) {
      result.push(nums[dq[0]]);
    }
  }
  return result;
}

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3, 3, 5, 5, 6, 7]

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindow {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>(); // indices, values decreasing
        int[] result = new int[nums.length - k + 1];
        int r = 0;
        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) {
                result[r++] = nums[dq.peekFirst()];
            }
        }
        return result;
    }
}

#include <stdlib.h>

// dq stores indices; values in nums[dq[...]] are decreasing.
int *maxSlidingWindow(int *nums, int numsSize, int k, int *returnSize) {
    int *dq = malloc(numsSize * sizeof(int));
    int head = 0, tail = 0; // [head, tail) is the deque
    int *result = malloc((numsSize - k + 1) * sizeof(int));
    int r = 0;
    for (int i = 0; i < numsSize; i++) {
        while (tail > head && nums[dq[tail - 1]] <= nums[i]) {
            tail--;                       // drop smaller tails
        }
        dq[tail++] = i;
        if (dq[head] <= i - k) {
            head++;                       // evict out-of-window front
        }
        if (i >= k - 1) {
            result[r++] = nums[dq[head]];
        }
    }
    free(dq);
    *returnSize = r;
    return result;
}

#include <deque>
#include <vector>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // indices, values decreasing
    vector<int> result;
    for (int i = 0; i < (int)nums.size(); i++) {
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();          // drop smaller tails
        }
        dq.push_back(i);
        if (dq.front() <= i - k) {
            dq.pop_front();         // evict out-of-window front
        }
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

Complexity

Approach	Time	Space
Naive re-scan	O(n·k)	O(n)
Deque (this lesson)	O(n)	O(k)

Each index enters and leaves the deque exactly once, so the two loops together do at most 2n operations. The deque never holds more than k indices, hence O(k) extra space.

When to use it

A monotonic deque is the go-to for windowed extremes

Whenever you need the min or max (or any "dominance" relation) over a sliding window, a monotonic deque turns O(n·k) into O(n). The same shape solves "shortest subarray with sum ≥ K" and constrained-jump DP. Pitfall: store indices, not values, or you cannot tell when the front has expired. For window sums instead of extremes, a prefix-sum or a simple running total is simpler — save the deque for min/max.

Practice

Recap

Naive per-window scanning is O(n·k); it re-derives a max that barely changed each step.
Keep a deque of indices whose values decrease front-to-back, so the front is always the max.
Each index is pushed and popped once, giving O(n) time and O(k) space.

Sliding Window Maximum

The problem

A first attempt

The insight

How it works

Slide in the new index

Push the new index

Evict the expired front

Record the maximum

The code

Complexity

When to use it

Practice

Recap

Deques

Sliding Window

Monotonic Stack

On this page

Sliding Window Maximum

Why do we store indices in the deque instead of the values themselves?

If we used < instead of <= when popping the back, would the result still be correct?

How would you adapt this to report the sliding window minimum?

Deques

Sliding Window

Monotonic Stack

On this page