Problem 10.5 · Queue, Deque and Monotonic QueueHard

Sliding Window Maximum

PatternMonotonic Deque Sliding Window: Fixed Size Top K with a Heap

What it teaches: The monotonic deque gives each window's maximum in O(n) total, beating a heap's O(n log n).

Practise it on judges as “Sliding Window Maximum”.

The problem

Given nums and a window size k, return the maximum of each window of k consecutive elements as it slides from left to right.

Example 1

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

Example 2

Input: nums = [1], k = 1
Output: [1]

Constraints

1 ≤ n ≤ 10⁵
1 ≤ k ≤ n

Pattern clues in the wording

→ Maximum of every fixed-size window
→ n up to 10⁵ and k up to n: O(n·k) too slow

These clues point to Monotonic Deque: Keep a deque of candidates in decreasing order so the front is always the max of the current window.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        return new int[nums.length - k + 1];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,3,-1,-3,5,3,6,7] k = 3	[3,3,5,5,6,7]
2	nums = [1] k = 1	[1]

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Max-heap with lazy removal · O(n log n)2. Optimal: monotonic deque · O(n)

Max-heap with lazy removal

Time O(n log n) Space O(n)

Push (value, index) into a max-heap. For each window, pop from the top while the top's index has left the window, then read the top.

Approach 1

import java.util.PriorityQueue;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] != a[0] ? Integer.compare(b[0], a[0]) : Integer.compare(b[1], a[1]));
        int[] out = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            heap.offer(new int[]{nums[i], i});
            if (i >= k - 1) {
                while (heap.peek()[1] <= i - k) heap.poll();
                out[i - k + 1] = heap.peek()[0];
            }
        }
        return out;
    }
}

Verdict: Works, but the deque is faster.

Optimal: monotonic deque

Time O(n) Space O(k)

Deque of indexes with decreasing values. For each i: drop the front if it's out of the window; drop from the back while values ≤ nums[i]; add i; once the window is full, the front is the maximum.

Approach 2

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

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++) {
            if (!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;
    }
}

Verdict: Every index enters and leaves the deque once.

Before you submit

Edge cases and common mistakes

Test these inputs

k = 1 (the array itself)
k = n (one maximum)
Decreasing input (deque grows to k)
Duplicates

Mistakes people make

Storing values in the deque (can't detect expiry).
Reading the maximum before the first window is full.

Interview

Follow-up questions

How would you get the minimum instead?

Command Palette