Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: Sliding Window Maximum
• Main tags: Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue

What the problem is really asking

The input gives an array and a window size k. Imagine placing a length-k window over the first k elements, recording the maximum value inside that window, then moving the window one step to the right and repeating until the end.

The output is the list of those window maximums.

The challenge is that the windows overlap heavily. When the window moves one step, almost all of the old window is still there. A good solution should reuse that structure instead of recomputing the maximum from scratch every time.

Why the brute-force solution is too slow

The most direct approach is:

1. For each window start index, scan the next k elements.
2. Compute the maximum.
3. Append it to the answer.

That costs O(k) work per window, and there are about n windows, so the total time is O(nk).

That is fine for small inputs, but it becomes too slow when both the array and the window are large. The real interview question is how to keep track of the maximum while the window is moving, without paying for a full rescan each time.

The key idea: keep only useful candidates

The optimal solution uses a monotonic deque.

The deque stores indices, not values. Those indices are kept in an order with two important rules:

1. The indices are always inside the current window.
2. Their values are in decreasing order from front to back.

That second rule is the whole trick.

If a new value is greater than or equal to some value at the back of the deque, the smaller value can never matter again. It is worse in two ways:

• it is smaller
• it is older, so it will leave the window sooner

So before pushing a new index, the algorithm removes every index at the back whose value is less than or equal to the new value.

After that cleanup, the front of the deque is always the maximum value for the current window.

How to derive this in an interview

A clean way to derive the solution is to start with the question: what information must survive when the window moves?

You do not need every number from the old window. You only need numbers that could still become the maximum of some future window.

That immediately tells you which elements are useless:

• anything that already fell out of the window
• anything smaller than a newer element to its right

Once those are removed aggressively, the remaining candidates form a decreasing queue. The maximum is always the front element, because every later candidate is smaller.

This leads naturally to the monotonic deque solution:

• remove expired indices from the front
• remove dominated indices from the back
• push the current index
• read the maximum from the front once the first full window is formed

A small example

Take nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3.

For the first window [1, 3, -1], the deque ends up representing [3, -1] by index, so the maximum is 3.

When -3 arrives, it gets appended because it does not remove 3 or -1. The window maximum stays 3.

When 5 arrives, it removes everything smaller than 5 from the back. That wipes out -3, -1, and even 3. Now 5 becomes the only serious candidate, which is exactly right because any future window containing 5 will never prefer those earlier smaller values.

That is the pattern for the whole algorithm: older weaker candidates get discarded the moment a stronger newer one appears.

Python solution

from collections import deque
from typing import Deque, List


class SlidingWindowMaximum:
    """Compute maximum values for every window using a monotonic deque."""

    def __init__(self, numbers: List[int], window_size: int) -> None:
        self.numbers = numbers
        self.window_size = window_size
        self.candidate_indices: Deque[int] = deque()

    def compute(self) -> List[int]:
        if not self.numbers or self.window_size == 0:
            return []

        if self.window_size == 1:
            return list(self.numbers)

        window_maximums: List[int] = []

        for current_index, current_value in enumerate(self.numbers):
            # Remove indices that are no longer inside the current window.
            self._discard_expired_indices(current_index)

            # Remove smaller-or-equal values from the back because the new
            # element is newer and at least as strong as a future maximum.
            self._discard_dominated_indices(current_value)

            self.candidate_indices.append(current_index)

            if self._window_has_formed(current_index):
                window_maximums.append(self.numbers[self.candidate_indices[0]])

        return window_maximums

    def _discard_expired_indices(self, current_index: int) -> None:
        leftmost_valid_index = current_index - self.window_size + 1

        while (
            self.candidate_indices
            and self.candidate_indices[0] < leftmost_valid_index
        ):
            self.candidate_indices.popleft()

    def _discard_dominated_indices(self, current_value: int) -> None:
        while (
            self.candidate_indices
            and self.numbers[self.candidate_indices[-1]] <= current_value
        ):
            self.candidate_indices.pop()

    def _window_has_formed(self, current_index: int) -> bool:
        return current_index + 1 >= self.window_size


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        solver = SlidingWindowMaximum(numbers=nums, window_size=k)
        return solver.compute()

Why this works

The deque always stores indices in decreasing value order. That means the index at the front is the largest value among all valid candidates in the current window.

Two invariants make the algorithm correct:

First, expired indices are removed from the front, so every stored index is guaranteed to belong to the current window.

Second, dominated indices are removed from the back. If nums[i] <= nums[j] and i < j, then index i is never more useful than j for any future window that contains both. j has a value at least as large and stays valid longer, so i can be discarded permanently.

Because each index is pushed once and popped at most once from either end, the total time is O(n). The extra space is O(k) because the deque only holds indices that are still relevant to the current window.

Interview follow-ups

What if the interviewer asks for a heap-based solution first?

A max-heap solution is a common stepping stone. The heap stores pairs like (-value, index) so the largest value appears on top. As the window moves, the algorithm pushes the new element and lazily pops heap entries whose indices are outside the current window. That approach is easier to discover if the monotonic deque is not obvious yet, and it is still correct. The tradeoff is complexity: each push and cleanup step costs O(log k), so the total time becomes O(n log k) instead of O(n).

What if the problem were sliding minimum instead of sliding maximum?

The structure stays the same, but the ordering flips. Instead of keeping the deque in decreasing order, it should stay in increasing order so the smallest value is always at the front. Every derivation step is identical: remove expired indices from the front, remove dominated candidates from the back, append the new index, and read the answer from the front. This is a good follow-up because it shows the technique is really about maintaining a monotonic queue, not about maxima specifically.

How would this work if numbers arrived as a stream?

The monotonic deque still works in a streaming setting as long as elements arrive left to right and the window size is fixed. Instead of iterating over a prebuilt array, the code would process one arriving value at a time, track its logical index, remove expired entries, remove dominated entries, and emit the current maximum whenever the first full window has formed. The time per new element remains amortized O(1), which is exactly why this approach is so useful in real systems that need rolling aggregates.

Practical takeaway

This problem becomes much simpler once the goal is phrased correctly: keep only the elements that could still become the maximum later.

The monotonic deque does exactly that. It removes elements that are too old from the front and elements that are too weak from the back. With those two cleanup rules in place, the front of the deque is always the window maximum, and the whole problem drops to linear time.