Sliding Window Maximum

HardMonotonic Queue · Sliding Window🧩 Queue & Monotonic Deque LeetCode #239 ↗Updated Oct 30, 2026

Problem

A window of fixed size k slides over the integer array nums from left to right, one position per step. Return an array holding the maximum value inside the window at each of its n - k + 1 positions.

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

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

1 ≤ n ≤ 10⁵ · -10⁴ ≤ nums[i] ≤ 10⁴ · 1 ≤ k ≤ n

Try it yourself

Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

An element that has a larger element to its right inside the window can never be a maximum again. Throw such elements away; what remains is a decreasing deque whose front is always the window maximum.

PatternQueue & Monotonic Deque

Instinct Arrival order matters, or you need the max/min of a moving window - reach for a FIFO queue, or a deque of indices kept in sorted order.

Memory hack Old ones leave by the front door, weak ones get bounced out the back - so whoever stands at the front is always the champion.

Open the Queue & Monotonic Deque guide →

Approaches

Brute ForceRescan Every Window

Time O(n · k)Space O(1) extra

For each start i, scan nums[i..i+k-1] and record the maximum. Consecutive windows share k-1 elements, yet we recompute everything from scratch.

Java

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] result = new int[nums.length - k + 1];
    for (int i = 0; i <= nums.length - k; i++) {
        int max = Integer.MIN_VALUE;
        for (int j = i; j < i + k; j++) max = Math.max(max, nums[j]);
        result[i] = max;
    }
    return result;
}

Correct, but up to ~2.5·10⁹ steps when k ≈ n/2.

BetterMax-Heap with Lazy Deletion

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

Push (value, index) pairs into a max-heap. The top is the maximum, but it may have slid out of the window — so before reading it, pop tops whose index < i - k + 1. Stale entries below the top are left alone, so the heap can grow to n (e.g. increasing input).

Java

public int[] maxSlidingWindow(int[] nums, int k) {
    PriorityQueue<int[]> maxHeap =
        new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
    int[] result = new int[nums.length - k + 1];
    for (int i = 0; i < nums.length; i++) {
        maxHeap.offer(new int[] {nums[i], i});
        while (maxHeap.peek()[1] < i - k + 1) maxHeap.poll(); // expired top
        if (i >= k - 1) result[i - k + 1] = maxHeap.peek()[0];
    }
    return result;
}

Big improvement, but the log factor and stale entries cost time and memory.

OptimalMonotonic Decreasing Deque of Indices

Time O(n)Space O(k)

The deque stores indices whose values are strictly decreasing. For each i: drop the front if it left the window, pop from the back every value < nums[i] (they are dominated forever), push i. The front is the answer.

Java

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

Dry run[1,3,-1,-3,5,3,6,7], k=3

i currentd in deque changed

i=2
1

3
d
-1
i d
-3

5

3

6

7

dq=[3,-1] → out 3
i=3
1

3
d
-1
d
-3
i d
5

3

6

7

out 3
i=4
1

3

-1

-3

5
i d
3

6

7

1 expired; pop -1,-3 → 5
i=5
1

3

-1

-3

5
d
3
i d
6

7

out 5
i=6
1

3

-1

-3

5

3

6
i d
7

pop 3, 5 → out 6
i=7
1

3

-1

-3

5

3

6

7
i d
pop 6 → out 7 ✔

Every index enters and leaves the deque once — linear and minimal.

Pro tip

Store indices, not values: you need them to detect when the front has expired.

At a glance

Level	Approach	Time	Space
Brute Force	Rescan Every Window	`O(n · k)`	`O(1) extra`
Better	Max-Heap with Lazy Deletion	`O(n log n)`	`O(n)`
Optimal	Monotonic Decreasing Deque of Indices	`O(n)`	`O(k)`

Common pitfalls

Storing values in the deque — you can no longer tell when the front leaves the window.
Checking expiry with the wrong bound: the window is [i-k+1, i].
Recording results before the first full window (i < k-1).

Interview tips

Explain domination: a smaller, older element is useless once a bigger one arrives.
Justify O(n) by amortisation — at most one push and one pop per index.
Mention the heap as a stepping stone and why lazy deletion keeps it correct.

Pattern

Monotonic deque → max/min over a sliding window, or DP transitions over a fixed-range window.

My notes saved in this browser