Sliding Window Maximum

1. Problem & Core Objective

The problem

You are given an array nums and a window of size k sliding from the very left to the very right. You can only see the k numbers in the window; each time it moves right by one position.

Return an array of the maximum in each window.

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

Window position                 Max
[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

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

What the interviewer is actually testing

This is the one question in the section where the standard window technique fails, and recognizing why is the point.

1. Do you see that a maximum can't be maintained like a sum? Removing an element from a sum is subtraction. Removing the current maximum leaves you with no idea what the new maximum is. That asymmetry is the whole problem.
2. Can you derive the monotonic deque? The insight is that some elements can be discarded permanently — a smaller element that arrives before a larger one can never be a maximum again.
3. Do you store indices rather than values? You need the index to know when an element has slid out of the window.
4. Can you prove it's O(n)? Each index is pushed once and popped at most once — the same aggregate argument as the monotonic stack.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 10^5, k up to n.

• O(n · k) → up to 10^10 when k ≈ n. Too slow.
• O(n log n) → fine.
• O(n) → the target.

Step 2 — Why the usual window trick doesn't work

For a sum, sliding is easy:

sum = sum - leaving + entering;      // O(1)

For a maximum, try the same thing:

max = ???                            // the leaving element WAS the max. Now what?

There's nothing to subtract. If the departing element was the maximum, the new maximum is the largest of the remaining k − 1 elements — and you have no record of them in any useful order. Recomputing it costs O(k), giving O(n · k) overall.

A max is not incrementally reversible the way a sum is. That's the obstacle, and it's worth stating explicitly before proposing a fix.

Step 3 — Look for elements that can be discarded

Suppose the window currently holds …, 3, … and a 7 arrives to its right.

Can the 3 ever be the maximum of a future window?

No. Any future window containing the 3 must also contain the 7 — because 7 is to the right of 3, so it leaves the window later. The 7 is both bigger and longer-lived. The 3 is permanently dominated.

When a new element arrives, every smaller element already in the window becomes useless forever.

Step 4 — What's left is a decreasing sequence

If you discard every dominated element, the survivors are in strictly decreasing order from oldest to newest:

values:  [7, 5, 2]        ← front is the largest and the oldest

The front is the window's maximum. The rest are the "next in line" — candidates that become the maximum once the ones ahead of them expire.

That's a monotonic deque: you evict from the back when a larger element arrives, and from the front when the oldest element slides out of the window.

Step 5 — Why indices, not values

Two evictions are needed, and they need different information:

• Back eviction compares values — is this element smaller than the incoming one?
• Front eviction compares positions — has this element slid out of the window?

Store indices, and you get both: the index directly, and the value via nums[index]. Storing values alone makes the front eviction impossible.

Step 6 — Why it's O(n)

Each index is pushed exactly once and popped at most once. So across the entire run the inner while executes at most n times in total, even though it looks nested. Total work is O(n).

Same aggregate argument as the monotonic stack (09) and Longest Consecutive Sequence.

3. Solution Paths

Approach 1 — Brute force: scan each window

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];

    for (int i = 0; i + k <= n; i++) {
        int max = nums[i];
        for (int j = i; j < i + k; j++) max = Math.max(max, nums[j]);
        res[i] = max;
    }
    return res;
}

• Time: O(n · k) — up to 10^10.
• Space: O(1) beyond the output.

Counter-questions on this approach

⭐ "Consecutive windows share k − 1 elements. What are you recomputing?"

Almost the entire maximum. Only one element leaves and one enters, yet I rescan all k. The natural fix would be to update the maximum incrementally — but that's exactly what a maximum doesn't allow, because removing the current maximum gives no information about the next one. Recognizing that obstacle is what leads to the deque.

"Is O(n · k) really that bad? k might be small."

It depends entirely on k, and the constraints allow k up to n. At k ≈ n/2 that's 2.5 × 10^9 operations. A solution whose complexity degrades with a parameter the problem lets grow is not a safe answer.

Approach 2 — Max-heap with lazy deletion

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];

    // max-heap of {value, index}
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);

    for (int i = 0; i < n; i++) {
        heap.offer(new int[]{nums[i], i});

        if (i >= k - 1) {
            while (heap.peek()[1] <= i - k) heap.poll();   // discard stale entries
            res[i - k + 1] = heap.peek()[0];
        }
    }
    return res;
}

How it works. Push everything. The heap's root is the largest value seen so far — but it may have slid out of the window. So before reading it, discard any root whose index is outside the window. This is lazy deletion: rather than paying O(n) to remove an arbitrary element from the heap, leave it and skip it when it surfaces.

• Time: O(n log n) — each element is pushed once and popped at most once, at O(log n) each.
• Space: O(n) — the heap can hold every element.

Counter-questions on this approach

⭐ "Why can't you just remove the departing element from the heap directly?"

Because PriorityQueue.remove(Object) is O(n) — the heap is only organized around its root, so finding an arbitrary element means scanning the backing array. Doing that once per slide would be O(n²). Lazy deletion sidesteps it: leave stale entries in place and discard them only when they reach the top, where they're O(1) to identify.

⭐ "Is the while loop that discards stale entries safe? Could it empty the heap?"

No. The element at index i was just pushed and is inside the window by definition, so the heap always contains at least one valid entry and peek() is never called on an empty heap. Worth checking rather than assuming — a while that pops without a bound is exactly where this kind of solution breaks.

"Why (a, b) -> b[0] - a[0] for a max-heap?"

Swapping the operands reverses the ordering. It's safe here because values are bounded by ±10^4 so the subtraction can't overflow. In general I'd write Integer.compare(b[0], a[0]) — subtraction comparators wrap and silently corrupt the ordering when values straddle the int range. See 04.

"This is O(n log n) — good enough?"

It passes, and it's a solid answer. But O(n) is achievable, and the gap comes from the heap maintaining more order than needed: it keeps all elements ranked when only the decreasing "front runners" can ever become the maximum. Discarding dominated elements entirely is what removes the log n.

Approach 3 — Monotonic deque (optimal)

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();     // holds INDICES; their values decrease front→back

    for (int i = 0; i < n; i++) {
        // 1. Evict from the FRONT: has the oldest candidate slid out of the window?
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();

        // 2. Evict from the BACK: anything smaller than the incoming value is now useless
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();

        dq.offerLast(i);

        // 3. Record once the first full window exists
        if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
    }
    return res;
}

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

Result: [3,3,5,5,6,7] ✓

Notice step i = 4: the arriving 5 evicts two elements from the back and the expired index 1 from the front — leaving only itself, correctly.

• Time: O(n) — each index pushed once, popped at most once.
• Space: O(k) — the deque never holds more than one window's worth.

Counter-questions on this approach

⭐ "Prove this is O(n). There's a while inside a for."

Each index is pushed onto the deque exactly once, at its own iteration. It can be popped at most once — from either end — and once popped it never returns. So across the entire run, the total number of pop operations is bounded by n. The inner while doesn't multiply the outer loop; it consumes from a budget of n pushes. Total work is O(n) — aggregate accounting, the same argument that makes a monotonic stack linear.

⭐ "Why store indices rather than the values themselves?"

Because the two evictions need different information. The back eviction compares values — is this candidate smaller than the arrival? The front eviction compares positions — has this candidate slid out of the window? Indices give me both: the position directly and the value via nums[index]. With values alone I could never tell whether the front element had expired.

"Why is the front eviction an if rather than a while?"

Because exactly one index enters per iteration, so at most one can expire per iteration. A while would be harmless but is unnecessary, and writing if signals that I reasoned about how many expirations are possible rather than defensively looping.

"Your back eviction uses <. What if you used <= instead?"

Both are correct. With <, equal values are kept, so the deque may hold duplicates; with <=, earlier equal values are evicted. The maximum is the same either way, since equal values give the same answer. < keeps the deque marginally larger but avoids discarding an element that might outlive the one that displaced it — irrelevant for the maximum, but it matters if you adapt this to report indices.

"Why does res have size n - k + 1?"

That's the number of windows: the first starts at index 0, the last starts at n - k. And res[i - k + 1] maps the window ending at i to its slot, since that window starts at i - k + 1. Worth checking on a small case: n = 8, k = 3 gives 6 windows, matching the expected output length.

Comparison

4. Why the Optimal Wins

Against brute force. Consecutive windows share k − 1 elements, and the brute force rescans all of them. The deque carries the useful information forward.

Against the heap. Both avoid rescanning, but the heap maintains more order than the problem needs. It keeps every element ranked — yet most of them can never be a maximum, because a larger element already sits to their right. The deque discards those permanently, and what remains needs no ranking structure at all: it's already decreasing by construction. Removing that unnecessary order is exactly what removes the log n.

The general principle: if your data structure maintains an invariant stronger than the question requires, there's usually a cheaper one.

That's the same observation behind preferring hashing over sorting in Section 1.

Space too. The heap can hold all n elements because stale entries accumulate until they surface. The deque is capped at k — it evicts expired indices eagerly from the front.

Why O(n) is the floor. Every element must be examined, and there are n − k + 1 outputs to write. So O(n) is optimal.

5. Java Prerequisites

ArrayDeque as a double-ended queue

Deque<Integer> dq = new ArrayDeque<>();

dq.offerLast(i);     // add to the back
dq.pollLast();       // remove from the back    — returns null if empty
dq.peekLast();       // read the back
dq.pollFirst();      // remove from the front
dq.peekFirst();      // read the front
dq.isEmpty();

This is the one problem in the 150 that genuinely needs both ends, which is why it's a deque rather than a stack or a queue. See 02 §5.

Use ArrayDeque, not LinkedList (poor cache behaviour) and not java.util.Stack (a legacy synchronized Vector, and single-ended anyway).

The offer/poll/peek family vs add/remove/get

dq.pollFirst();      // returns null on empty
dq.removeFirst();    // throws NoSuchElementException on empty

Prefer the null-returning family, guarded by isEmpty() checks as above. Mixing the two families is a common source of unexpected exceptions.

ArrayDeque rejects null

It uses null internally to mark empty slots. Storing Integer indices is fine — they're never null here — but it's why you can't use ArrayDeque as a general nullable queue.

Autoboxing

Deque<Integer> dq = new ArrayDeque<>();
dq.offerLast(i);                 // int i is autoboxed to Integer
nums[dq.peekLast()]              // Integer auto-unboxed back to int for the index

Both conversions are implicit. The unboxing in nums[dq.peekLast()] would throw if the deque were empty and peekLast returned null — which is why every access is guarded by !dq.isEmpty().

Output sizing

int[] res = new int[n - k + 1];
res[i - k + 1] = ...;

There are n - k + 1 windows. The window ending at index i starts at i - k + 1, which is its slot. Verify on n = 8, k = 3: 6 windows, and the window ending at i = 2 writes to res[0].

6. Interview Communication Guide

Clarifying questions

1. "Is k guaranteed to be at most n?" — yes, per the constraints, so no empty-window case.
2. "Do I return the maximum values, or their indices?" — the values here; indices would be a one-line change since the deque already stores them.
3. "Can values be negative?" — yes, which matters if you were tempted to initialize a running maximum to 0.
4. "Is k = 1 possible?" — yes, and the answer is just nums itself. Good sanity check.
5. "Can I assume the array is non-empty?" — yes, n >= 1.

The pitch

"The brute force rescans each window for its maximum — O(n·k), which is 10^10 when k is large.

The natural fix would be to update the maximum incrementally the way you'd update a sum. But that doesn't work: removing an element from a sum is subtraction, whereas if the departing element was the maximum, you have no idea what the new one is. A maximum isn't reversible.

So instead of maintaining the maximum, I'll maintain the candidates. Here's the key observation: if a new element arrives and there's a smaller element already in the window, that smaller one can never be a maximum again — any future window containing it also contains the newer, larger element, which survives longer.

Discarding all such dominated elements leaves a strictly decreasing sequence, whose front is the current maximum. I keep that in a deque: evict from the back when a bigger element arrives, and from the front when the oldest index slides out of the window.

I store indices, not values, because the back eviction compares values while the front eviction compares positions — indices give me both.

O(n) time: each index is pushed once and popped at most once, so the inner loop is amortized constant. O(k) space.

There's also a heap solution at O(n log n) using lazy deletion, which is a reasonable answer — the deque beats it because a heap ranks all elements when only the decreasing front-runners can ever matter."

Edge cases to raise proactively

The strictly decreasing case is the one to volunteer — it's the worst case for space, since no element is ever dominated and the deque fills to k. It's also the case that proves the space bound is O(k) and not O(1).

All-negative input is worth mentioning too: it catches any solution that initializes a running maximum to 0.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "Sliding window minimum instead of maximum."

Flip one comparison: evict from the back while nums[dq.peekLast()] > nums[i], keeping an increasing deque. Everything else is identical. If you need both simultaneously, run two deques in the same pass — still O(n).

"What if k changed for each query, over the same array?"

The deque solution is O(n) per query, so q queries cost O(q · n). To do better, precompute a sparse table for range-maximum queries: O(n log n) preprocessing, then any window maximum in O(1). That's the right structure when k varies but the array doesn't.

"What if elements could be updated between queries?"

A sparse table is static, so it can't handle updates. Use a segment tree: O(log n) per update and O(log n) per range-maximum query. The deque doesn't apply at all once the array is mutable, which is worth saying plainly.

"What if the array streams in and you can't store it?"

The deque already works: it holds at most k indices and never looks backwards into the array beyond what it retains. You'd store the values alongside the indices rather than dereferencing nums, giving O(k) memory — genuinely streaming.

"What about the maximum of every subarray rather than every fixed window?"

A different problem. The sum of all subarray maxima is solved with a monotonic stack, computing for each element how many subarrays it dominates — O(n). Worth noting the deque here and that stack are the same idea applied to different window semantics.

"What if you needed the j-th largest in each window, not the largest?"

The deque's dominance argument collapses — a smaller element can still be the j-th largest even with a bigger one to its right, so nothing can be discarded. You'd need two heaps or an order-statistic tree (or a TreeMap with counts) giving O(n log k). Recognizing that the pruning argument breaks is the key insight, not producing the alternative.

"What if k could exceed the array length?"

The constraints forbid it, but defensively you'd return either an empty array or a single-element array containing the global maximum, depending on the agreed contract. Worth clarifying rather than guessing.