Why does a monotonic deque solve Sliding Window Maximum?

The deque keeps indexes whose values decrease from front to back. When a new value arrives, every smaller value behind it can never be a window maximum again — the new value is larger and stays in the window longer — so they are popped. The front is then always the largest value in the window, and it leaves only when its index slides out.

What is the time complexity of the deque solution?

O(n). Each index is pushed onto the deque once and removed at most once, from the front or the back, so the total work across the inner loop is O(n) even though one step can pop several indexes. The deque holds at most k indexes, so space is O(k).

Why store indexes in the deque instead of values?

The front must be dropped once it falls outside the window, and only its index says when that happens. The value is always one lookup away, nums[index].

Sliding Window Maximum

Return the maximum of every window of size k in O(n) with a monotonic deque that keeps only indexes that could still become a maximum.

HardSolve on LeetCode

Problem Understanding

Sliding Window Maximum: given an array nums and a window size k, slide the window from left to right one position at a time and return the maximum of each window.

Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 returns [3, 3, 5, 5, 6, 7].

Attempt 1: Scan Every Window

Take the maximum of each of the n − k + 1 windows directly: O(n·k), which is quadratic when k is about n/2. A max-heap of (value, index) pairs improves it to O(n log n), discarding tops that have left the window. Both redo work the previous window already did.

The Intuition: Smaller Values Behind a Larger One Are Useless

Suppose the window holds 3 at index 1 and then 5 arrives at index 4. While 5 is in the window, 3 can never be the maximum — and 5 arrived later, so it stays in the window longer. 3 can be forgotten for good.

Keeping only values that could still become a maximum leaves a decreasing sequence, stored as indexes in a deque:

Expire: if the front index has slid out (≤ i − k), drop it from the front.
Pop: drop every back index whose value is smaller than nums[i], then push i on the back.
Record: once the first window is full, the front holds the maximum.

This is a fixed-length sliding window paired with a monotonic structure — the same idea as a monotonic stack, but with removals at both ends.

Interactive Walkthrough

k = 3 · DEQUE FRONT = WINDOW MAX

EMPTY DEQUE

-1

-3

result

no full window yet

Window max

—

Deque size

deque (front → back)

Empty

The deque holds indexes whose values decrease front to back; its front is the window maximum. k = 3

Read nums[0] = 1. The window is now indexes 0..0

nums

The window is framed over nums. Indexes in the deque are filled, with the front — the current maximum — in green; an index just dropped is struck out. Watch 5 arrive and clear every smaller value out of the deque at once.

Dry Run Table

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

`i`	`nums[i]`	Removed	Deque after	Window max
0	1	—	`[1]`	—
1	3	pop 1	`[3]`	—
2	−1	—	`[3, −1]`	3
3	−3	—	`[3, −1, −3]`	3
4	5	expire 3; pop −3, −1	`[5]`	5
5	3	—	`[5, 3]`	5
6	6	pop 3, 5	`[6]`	6
7	7	pop 6	`[7]`	7

Return [3, 3, 5, 5, 6, 7].

The Solution Template

A deque of indexes with decreasing values.

Sliding Window Maximum Code

1var maxSlidingWindow = function(nums, k) {
2    const dq = [];
3    let head = 0;
4    const result = [];
5    for (let i = 0; i < nums.length; i++) {
6        if (head < dq.length && dq[head] <= i - k) {
7            head++;
8        }
9        while (head < dq.length && nums[dq[dq.length - 1]] < nums[i]) {
10            dq.pop();
11        }
12        dq.push(i);
13        if (i >= k - 1) {
14            result.push(nums[dq[head]]);
15        }
16    }
17    return result;
18};

Edge Cases & Common Mistakes

k = 1: every value is its own window maximum; the result is nums.
k = n: one window, one maximum.
Decreasing input ([9, 7, 5, 3, 1]): nothing is popped from the back; maximums leave only by expiring from the front.
Increasing input ([1, 2, 3, 4, 5]): each new value pops everything, so the deque never holds more than one index.
Equal values: pop only strictly smaller values (<) or use ≤ — both are correct, as long as the expiry check uses indexes.
Storing values instead of indexes: there is then no way to tell when the front has left the window.

Summary

Keep a deque of indexes with decreasing values: expire the front when it leaves the window, pop smaller values from the back before pushing, and read each window's maximum from the front. O(n) time, O(k) space.

Maximum Sum of Distinct Subarrays With Length K