Sliding Window Maximum (LC 239)

Pattern: Monotonic Deque
Difficulty: Hard
Key Concept: An element that is smaller than a later element can never be the window max again — evict it immediately. What survives is a decreasing deque of indices whose front is always the answer.

Problem Statement

Given nums[] and a window size k, the window slides one position at a time from left to right. Return an array of the maximum in each window position.

Input: int[] nums, int k, 1 <= k <= nums.length <= 10^5
Output: int[] of length n - k + 1

Example

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

 [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

---

1. Algorithm & Pseudocode

Brute force

for i from 0 to n-k:
    max = -infinity
    for j from i to i+k-1:
        max = max(max, nums[j])
    res[i] = max

Better (max-heap with lazy deletion)

heap of {value, index}, ordered by value descending
for i from 0 to n-1:
    heap.push({nums[i], i})
    while heap.top.index <= i - k: heap.pop()     // discard stale entries
    if i >= k-1: res[i-k+1] = heap.top.value

Optimal (monotonic deque)

dq = empty deque of INDICES, values decreasing front→back

for i from 0 to n-1:
    1. EVICT FRONT  : if dq.front <= i - k, pollFirst        // slid out of window
    2. EVICT BACK   : while nums[dq.back] <= nums[i], pollLast  // dominated forever
    3. PUSH         : offerLast(i)
    4. RECORD       : if i >= k-1, res[i-k+1] = nums[dq.front]

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why the brute force fails Every window re-reads all k elements and throws the work away. With n = 10^5 and k = 10^4 that’s ~10^9 comparisons. TLE.

2. First improvement: a heap Keep a max-heap of {value, index}. The top might be stale (already slid out), so pop while the top’s index is out of range. This is lazy deletion — you never search the heap for an element to remove, you just ignore it until it surfaces. O(n log n), and a perfectly respectable answer to give first.

3. The key observation that beats the heap Suppose j < i and nums[j] <= nums[i]. Any window containing j and still valid must also contain i (since i is later and the window slides right). So nums[j] can never be the max again — nums[i] dominates it forever. Delete j on the spot. No heap needed, no comparisons deferred.

4. What that leaves you with After applying that rule, the surviving indices always have strictly decreasing values from front to back. Therefore the front is the maximum of everything currently in play. Reading the answer is O(1).

5. Two different evictions, don’t confuse them

   • Front eviction is about time: index has fallen out of the window (dq.peekFirst() <= i - k).
   • Back eviction is about value: dominated by the incoming element. They are independent and both are necessary.

6. Store indices, not values You need the index to decide whether the front has slid out of the window. Values alone can’t tell you that.

7. Why O(n) Each index is offerLast-ed exactly once and removed at most once (from either end). Total deque operations ≤ 2n.

---

3. The Dry Run

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

i	nums[i]	Front evict	Back evict	Deque (indices)	Window max
0	1	—	—	[0]	(not full)
1	3	—	pop 0 (1 <= 3)	[1]	(not full)
2	-1	—	— (3 > -1)	[1,2]	nums[1] = 3
3	-3	—	— (-1 > -3)	[1,2,3]	nums[1] = 3
4	5	pop front 1 (1 <= 4-3=1)	pop 3, pop 2	[4]	nums[4] = 5
5	3	—	— (5 > 3)	[4,5]	nums[4] = 5
6	6	—	pop 5, pop 4	[6]	nums[6] = 6
7	7	—	pop 6	[7]	nums[7] = 7

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

Visual — the deque as a “descending staircase”

after i=3:   front                back
             [ idx1 ][ idx2 ][ idx3 ]
             val 3    val -1   val -3      ← strictly decreasing, front = current max

i=4 arrives with value 5:
   • idx1 has slid out of the window  → pollFirst
   • 5 dominates -1 and -3            → pollLast, pollLast
             [ idx4 ]
             val 5                          ← the staircase collapsed to one step

---

4. Java Solution

Brute Force

class Solution {
    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 = Integer.MIN_VALUE;
            for (int j = i; j < i + k; j++) max = Math.max(max, nums[j]);
            res[i] = max;
        }
        return res;
    }
}

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

Better: Max-Heap with lazy deletion

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        // {value, index}; max-heap by value. Integer.compare avoids b[0]-a[0] overflow.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));

        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) pq.poll();      // drop stale tops
            if (i >= k - 1) res[i - k + 1] = pq.peek()[0];
        }
        return res;
    }
}

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

Optimal: Monotonic Deque

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

        for (int i = 0; i < n; i++) {
            // 1. front has slid out of the window
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();

            // 2. nums[i] dominates everything smaller at the back — they can never win again
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();

            // 3. this index is a live candidate
            dq.offerLast(i);

            // 4. once the first full window exists, the front IS the max
            if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
        }
        return res;
    }
}

Time O(n) · Space O(k) — the deque never holds more than k indices

Sliding-window minimum is the identical code with <= flipped to >= in step 2.

---

5. The “Java vs. Others” Edge

• ArrayDeque is the right class — O(1) at both ends, array-backed (cache-friendly), and unsynchronized. LinkedList also implements Deque but allocates a node per element and chases pointers; measurably slower on a 10^5 hot loop.
• peekFirst/pollFirst/peekLast/pollLast return null on empty; getFirst/removeFirst throw. Use the null-returning family plus an isEmpty() guard — but the guard must come first in the &&, because unboxing a null Integer throws NPE.
• Comparator overflow: (a, b) -> b[0] - a[0] silently breaks when values straddle Integer.MAX_VALUE/MIN_VALUE. Always Integer.compare(b[0], a[0]). Interviewers plant this.
• PriorityQueue is not FIFO and its iterator is not in heap order — only poll() gives ordering. Don’t iterate a heap expecting sorted output.
• Boxing: Deque<Integer> boxes indices above 127. An int[] dq = new int[n] with head/tail cursors is the allocation-free version — worth naming if asked to optimise.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute force	O(n·k)	O(1)	Rescans every window; TLE
Max-heap + lazy deletion	O(n log n)	O(n)	Heap can hold stale entries
Monotonic deque	O(n)	O(k)	Each index enters/leaves once

---

7. Edge Cases & Follow-Ups

• k == 1 → the answer is nums itself; the deque holds one index at a time.
• k == n → a single window; deque work reduces to finding the global max.
• All equal values ([5,5,5,5]) — with <= in the back-eviction, equal values are also evicted. Still correct, because the newer index survives longer and has the same value.
• Duplicates and < vs <= — using < keeps duplicates in the deque. Both give the right max; <= keeps the deque smaller. Know that you chose deliberately.
• Follow-up: sliding window median → LC 480, needs two heaps (or a TreeMap), not a deque — a deque can only maintain an extreme, not an order statistic.

---

Related Problems

#	Problem	Difficulty	Connection
LC 1438	Longest Subarray with Absolute Diff ≤ Limit	Medium	two deques: one max, one min
LC 862	Shortest Subarray with Sum at Least K	Hard	monotonic deque over prefix sums
LC 1696	Jump Game VI	Medium	DP + sliding-window max of the DP array
LC 480	Sliding Window Median	Hard	two heaps / TreeMap, not a deque
LC 739	Daily Temperatures	Medium	sibling monotonic stack pattern