Sliding Window Maximum Explained

Given an array and a window size k, report the maximum of every window as it slides. The naive solution scans each window at O(n·k). A heap gets it to O(n log k). A monotonic deque gets it to O(n), and the reason it works is that most elements can be discarded the moment a larger one arrives behind them.

Written against Java 17.

The problem

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

windows:  [1  3 -1] -3  5  3  6  7   -> 3
           1 [3 -1 -3] 5  3  6  7    -> 3
           1  3 [-1 -3 5] 3  6  7    -> 5
           1  3 -1 [-3  5 3] 6  7    -> 5
           1  3 -1 -3 [5  3 6] 7     -> 6
           1  3 -1 -3  5 [3  6 7]    -> 7

There are n - k + 1 windows, so the output length is fixed and can be allocated up front.

The key observation

If nums[i] <= nums[j] and i < j, then nums[i] can never be the maximum of any window that also contains j. It is smaller and it leaves the window earlier, so j beats it now and for the rest of its life.

That means most elements are irrelevant as soon as a larger one appears after them, and they can be discarded permanently rather than compared again.

What remains is a decreasing sequence of candidates: the current maximum, then the largest element that will still be in the window after the current maximum leaves, and so on. That sequence is the deque.

The implementation

static int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0 || k <= 0) return new int[0];

    int[] result = new int[nums.length - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();      // holds INDICES, decreasing by value

    for (int i = 0; i < nums.length; i++) {

        // 1. drop indices that have left the window
        if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }

        // 2. drop indices whose values can never win again
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }

        deque.offerLast(i);

        // 3. once the first window is complete, the front is the answer
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

O(n) time and O(k) space.

Why it is O(n) despite the inner while

The while loop looks like it makes this quadratic. It does not, and the argument is amortised: each index is added to the deque exactly once and removed at most once. The total work across the whole outer loop is therefore bounded by 2n, regardless of how many iterations any single while runs.

That is the same reasoning that makes the variable-size sliding window linear, and it is the standard place people mis-estimate complexity by reading the nesting rather than counting the total operations.

Indices, not values

The deque holds indices. Storing values instead makes step 1 impossible. There is no way to tell whether the front element has left the window without knowing where it came from.

deque.peekFirst() <= i - k is that check: the window currently covers i - k + 1 through i, so any index at or below i - k is outside it. Writing < i - k leaves one stale index in place, and the reported maximum is one position out of date, which produces a wrong answer only when the departing element was the maximum.

An if rather than a while in step 1 is sufficient because at most one index leaves per step, the window advances by one.

The <= in step 2

while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i])

With <=, equal values are discarded. With <. They are kept.

Both produce the correct maxima, because equal values give the same answer either way. <= keeps the deque smaller, and it means the deque holds strictly decreasing values, which is easier to reason about. Keeping duplicates costs memory and no correctness.

Tracing it

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

i	nums[i]	deque before	evicted	deque after	output
0	1	—	—	0	—
1	3	0	index 0 (1 ≤ 3)	1	—
2	−1	1	—	1 2	3
3	−3	1 2	—	1 2 3	3
4	5	1 2 3	3, 2, 1	4	5
5	3	4	—	4 5	5
6	6	4 5	5, 4	6	6
7	7	6	6	7	7

Step i = 4 shows the cascade: a single large value clears three candidates at once, which is why the average cost per element stays constant even though that one step did three evictions.

Against the alternatives

Approach	Time	Space	Note
Rescan each window	O(n·k)	O(1)	fine for tiny k
Max-heap of values	O(n log n)	O(n)	cannot remove the departing element cheaply
Max-heap with lazy deletion	O(n log n)	O(n)	discard stale entries at the top
Monotonic deque	O(n)	O(k)

The heap version deserves a note, because it is the reflexive answer and it has a real flaw: PriorityQueue.remove(Object) is O(n), so evicting the element that just left the window is linear. The workaround is lazy deletion — push (value, index) pairs and discard entries at the top whose index has expired:

PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
// ... push new int[] {nums[i], i}
while (heap.peek()[1] <= i - k) heap.poll();

That is correct and O(n log n), and the heap can grow to n entries rather than k, the deque is better on every axis; the heap is worth knowing as the fallback when the window rule is more complex than “the last k elements”.

Edge cases

• k = 1 — every element is its own maximum; the deque never holds more than one index.
• k equals the length — one window, and the deque behaves as a running maximum.
• k greater than the length — no valid window. Validate; the result array size would be negative.
• All decreasing — the deque grows to k and evicts one per step. This is the memory worst case.
• All increasing — the deque holds one index at a time; every new element clears it.
• Duplicates — handled by the <=; equal values do not accumulate.

The general pattern

A monotonic deque applies whenever a sliding window needs an extreme value and elements can be ruled out permanently by a later arrival. Reversing the comparison gives the sliding-window minimum unchanged in every other respect.

The same structure solves “the shortest subarray with sum at least k” over prefix sums, and the “largest rectangle in a histogram” family — both keep a monotonic sequence and pop when a new element invalidates the tail.

The recognition cue is a window plus an extreme, together with the property that an element beaten by a later one is beaten for good.

More in the algorithms guides, and Queue and Deque for the data structure.

Frequently asked questions

Why does the deque store indices instead of values?

To tell whether the front element has left the window. A value carries no position, so the expiry check is impossible.

Why is it O(n) when there is a while loop inside the for loop?

Each index is added once and removed at most once, so the total work across the whole run is bounded by 2n regardless of any single iteration.

What is the window-expiry condition?

deque.peekFirst() <= i - k. The window covers i - k + 1 to i, so anything at or below i - k is outside it.

Why is an if enough for the expiry check?

The window advances by one position per step, so at most one index can leave.

Should the eviction comparison be < or <=?

Either is correct. <= discards equal values and keeps the deque smaller, so the stored values are strictly decreasing.

Why not use a heap?

PriorityQueue.remove(Object) is O(n), so evicting the departing element is linear. Lazy deletion fixes that at O(n log n) and O(n) space — still worse than the deque.

What is the space complexity?

O(k), the deque holds at most one full window, which happens on a strictly decreasing input.

When does the first output appear?

At i == k - 1, when the first complete window exists. Earlier iterations only build the deque.

How do I get the sliding-window minimum instead?

Reverse the comparison in the eviction step. Nothing else changes.

What if k is larger than the array?

There is no valid window — validate up front, since the result array length would be negative.