20.Sliding Window Maximum

HardSliding Window · 6/6

Problem

You are given an integer array nums and a window size k. A window of size k slides from the left end of the array to the right end, one position at a time.

Return an array containing the maximum value of each window — there are n - k + 1 windows in total.

Examples

Input:  nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation:
  [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

Input:  nums = [1], k = 1
Output: [1]

Constraints

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

💡 Key Insight

Once a larger element arrives, every smaller element to its left can never be a window maximum again — the larger one is newer and outlives them. So keep a deque of indices whose values are strictly decreasing: pop smaller values from the back when a new element arrives, and pop the front when it slides out of the window. The front is always the current maximum, and each index is pushed and popped once.

Brute Force

TimeO(n · k)SpaceO(1)

Intuition

For each of the n - k + 1 windows, scan its k elements and take the maximum.

Algorithm

Create result of size n - k + 1.
For each start i, compute max(nums[i..i+k-1]) and store it in result[i].
Return result.

Visualization

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

i=0: max(1, 3, -1)  = 3
i=1: max(3, -1, -3) = 3
i=2: max(-1, -3, 5) = 5
...  each window rescanned from scratch

Code

java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        for (int i = 0; i + k <= n; i++) {
            int max = nums[i];
            for (int j = i + 1; j < i + k; j++) {
                max = Math.max(max, nums[j]);
            }
            result[i] = max;
        }
        return result;
    }
}

Complexity

Time: O(n · k) — up to 10^10 operations at the limits, which times out.
Space: O(1) — excluding the output.

Max-Heap with Lazy Deletion

TimeO(n log n)SpaceO(n)

Intuition

A max-heap gives the largest element quickly. Store (value, index) pairs. We do not remove elements as they leave the window (that would be O(k) in a PriorityQueue); instead, when we read the top, we discard it if its index is already outside the window. Stale entries are removed only when they bubble to the top.

Algorithm

Max-heap ordered by value (descending).
For each i: push (nums[i], i).
Once i >= k - 1: while the top's index <= i - k, poll it. The top is the window max → result[i - k + 1].
Return result.

Dry Run

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

i=2: heap top (3, idx1) in window [0..2]          → 3
i=3: top (3, idx1) in window [1..3]               → 3
i=4: push 5 → top (5, idx4)                       → 5
i=5: top (5, idx4) in window [3..5]               → 5
i=6: push 6 → top (6, idx6)                       → 6
i=7: push 7 → top (7, idx7)                       → 7

Code

java

import java.util.PriorityQueue;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        // entries are {value, index}; larger value first
        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) {
                // lazily drop maxima that slid out of the window
                while (heap.peek()[1] <= i - k) {
                    heap.poll();
                }
                result[i - k + 1] = heap.peek()[0];
            }
        }
        return result;
    }
}

Complexity

Time: O(n log n) — each element is pushed and polled at most once, at O(log n) each (the heap can hold stale entries, so its size is bounded by n, not k).
Space: O(n) — the heap in the worst case (e.g. increasing input keeps nothing stale on top, so nothing is removed).

Monotonic DequeOptimal

TimeO(n)SpaceO(k)

Intuition

Keep a deque of indices whose values are in decreasing order from front to back.

Arrive: before adding index i, pop from the back every index whose value is <= nums[i]. Those elements are older and not larger, so they can never be a maximum while i is in the window.
Expire: if the front index is <= i - k, it has left the window — pop it from the front.
Answer: the front holds the maximum of the current window.

Algorithm

Empty ArrayDeque<Integer> dq of indices.
For each i from 0 to n - 1:
- If dq.peekFirst() == i - k, pollFirst().
- While dq is non-empty and nums[dq.peekLast()] <= nums[i], pollLast().
- offerLast(i).
- If i >= k - 1, result[i - k + 1] = nums[dq.peekFirst()].
Return result.

Dry Run

flowchart TD
    A["i=0 (1): dq = [1]"] --> B["i=1 (3): pop 1 → dq = [3]"]
    B --> C["i=2 (-1): dq = [3, -1]<br/>output 3"]
    C --> D["i=3 (-3): dq = [3, -1, -3]<br/>output 3"]
    D --> E["i=4 (5): 3 expired; pop -3, -1<br/>dq = [5], output 5"]
    E --> F["i=5 (3): dq = [5, 3]<br/>output 5"]
    F --> G["i=6 (6): pop 3, 5 → dq = [6]<br/>output 6"]
    G --> H["i=7 (7): pop 6 → dq = [7]<br/>output 7"]

(The deque stores indices; values are shown for readability.)

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

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

        for (int i = 0; i < n; i++) {
            // remove the front index if it has slid out of the window
            if (!dq.isEmpty() && dq.peekFirst() == i - k) {
                dq.pollFirst();
            }
            // smaller-or-equal older values can never be a max again
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);
            // window [i-k+1, i] is complete: front is its maximum
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return result;
    }
}

Complexity

Time: O(n) — every index is added once and removed at most once.
Space: O(k) — the deque never holds more than k indices (excluding the output).

Complexity Comparison

Approach	Time	Space
Brute Force	O(n · k)	O(1)
Max-Heap (lazy deletion)	O(n log n)	O(n)
Monotonic Deque	O(n)	O(k)

Common Pitfalls

Storing values instead of indices in the deque — then you cannot tell when the front has left the window (duplicates make it ambiguous).
Using b[0] - a[0] style comparators is safe here only because values are within ±10^4; for wider ranges use Integer.compare to avoid overflow.
Comparing Integer objects with == (e.g. dq.peekFirst() == i - k works because one side is an int and unboxing happens; comparing two Integers with == would not be safe).
Writing the output before the first full window exists — only emit once i >= k - 1.