Lesson 4 of 16 Arrays and Strings

Sliding Window Maximum (Monotonic Deque)

Sliding window maximum in O(n) with a monotonic deque: intuition, a dry run, Python and Java code, and a 2000-case check against brute force.

40-50 min advanced 0/16 lessons done
Course contents Lesson 4 of 16 · 0 done
On this page (11 sections)
  1. What you will learn
  2. The problem
  3. The key insight
  4. Dry run
  5. Python
  6. Java
  7. Why it’s O(n)
  8. Related problems
  9. Key takeaways
  10. Exercises
  11. Quiz

What you will learn

  • Why the obvious approaches to sliding window maximum are too slow.
  • The monotonic deque: which elements to keep and why.
  • A full dry run, plus Python and Java solutions.

The problem

Given an array nums and a window size k, return the maximum of every window of k consecutive elements (LeetCode 239). For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the answer is [3, 3, 5, 5, 6, 7].

Approaches:

ApproachTimeProblem
max() of every windowO(n·k)Too slow when n and k are both 10⁵
Max-heap with lazy deletionO(n log n)Works, but heavier and more code
Monotonic dequeO(n)Each index is pushed and popped at most once

The key insight

When a new value x enters the window, any older, smaller-or-equal value can never be a maximum again: x is at least as big and will stay in the window longer. So throw those values away.

What remains, read from front to back, is a decreasing sequence of candidates. The front is the current maximum. The only other cleanup: if the front index has slid out of the window, drop it.

The deque stores indices, not values, so we can tell when an element has left the window.

Dry run

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 (deque shown as values):

ixPop from backDeque afterFront expired?Output
01none[1]nonone
131[3]nonone
2-1none[3, -1]no3
3-3none[3, -1, -3]no3
45-3, -1, 3[5]no5
53none[5, 3]no5
663, 5[6]no6
776[7]no7

Python

"""Sliding window maximum in O(n) with a monotonic deque (LeetCode 239)."""
import random
from collections import deque


def max_sliding_window(nums, k):
    dq = deque()  # indices; their values are strictly decreasing from front to back
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()          # smaller values can never be a max while x is in the window
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()      # front index slid out of the window
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out


def brute_force(nums, k):
    return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]


if __name__ == "__main__":
    print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
    random.seed(7)
    for _ in range(2000):
        nums = [random.randint(-20, 20) for _ in range(random.randint(1, 40))]
        k = random.randint(1, len(nums))
        assert max_sliding_window(nums, k) == brute_force(nums, k)
    print("2000 random tests match brute force")

Output:

[3, 3, 5, 5, 6, 7]
2000 random tests match brute force

Random testing against a brute force is a habit worth copying: it catches off-by-one errors in the expiry check (dq[0] <= i - k) quickly.

Java

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

public class SlidingWindowMax {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] out = new int[nums.length - k + 1];
        Deque<Integer> dq = new ArrayDeque<>(); // indices, values decreasing front to back
        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
            dq.offerLast(i);
            if (dq.peekFirst() <= i - k) dq.pollFirst();
            if (i >= k - 1) out[i - k + 1] = nums[dq.peekFirst()];
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }
}

Output:

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

Why it’s O(n)

Every index is appended once and removed at most once (from the back when a bigger value arrives, or from the front when it expires). That’s at most 2n deque operations in total, even though there’s a while inside the loop. Extra space is O(k).

  • Sliding window minimum: flip the comparison so the deque is increasing.
  • Shortest subarray with sum at least K (LeetCode 862): a monotonic deque over prefix sums.
  • Constrained subsequence sum (LeetCode 1425): DP where each state needs the max of the previous k states.
  • Jump game VI (LeetCode 1696): same DP-plus-window-max idea.

This pattern sits with monotonic stacks on the cheat sheet: monotonic stack / deque problems. The next lessons cover prefix sums and the stack version of the idea in monotonic stack.

Key takeaways

  • Keep a deque of indices whose values are decreasing; the front is the window maximum.
  • Pop smaller-or-equal values from the back before pushing; pop the front when it leaves the window.
  • Store indices, not values, so you can detect expiry.
  • O(n) time because each index enters and leaves the deque once.

Exercises

  1. Modify the code to return window minimums.
  2. Return both max and min for every window in one pass with two deques.
  3. Solve “longest subarray where max − min ≤ limit” (LeetCode 1438) with two deques and a variable window.

Quiz

  1. Why can a smaller, older value be discarded when a bigger value arrives?
  2. Why does the deque hold indices instead of values?
  3. What is the time complexity, and why isn’t the inner while loop O(k) per step overall?
Show answers
  1. The new value is larger and will stay in the window at least as long, so the older value can never be the maximum of any future window.
  2. To know when the front element has slid out of the window (index <= i - k).
  3. O(n): each index is pushed once and popped at most once, so the total work of all inner loops is bounded by n.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).