191. Sliding Window Maximum

For each window position, scan all k elements to find the maximum.

Brute Force

For each window starting at index i (from 0 to n-k), scan the k elements nums[i..i+k-1] and record the maximum. This gives O(n*k) time since we have (n-k+1) windows each requiring O(k) work.

Space is O(n-k+1) for the output array, which is O(n).

Why it's slow: each window overlaps with the previous by k-1 elements, yet we re-examine all of them.

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 <= n - k; i++) {
            int windowMax = nums[i];
            for (int j = i; j < i + k; j++) {
                windowMax = Math.max(windowMax, nums[j]);
            }
            result[i] = windowMax;
        }
        return result;
    }
}

Maintain a deque of indices in decreasing order of their values. The front of the deque is always the maximum of the current window. When sliding right, remove indices that fell out of the window and remove smaller values from the back.

Mental Model

Imagine a queue of candidates for "window maximum". A candidate is useless if a larger-or-equal value is ahead of it and also inside the window. So we keep only a decreasing sequence of values. The front is always the current max.

Algorithm Steps

1. Create an empty deque dq (stores indices, not values).
2. For each index i from 0 to n-1: a. Remove expired: While the front of dq is outside the window (index <= i - k), pop it from the front. b. Remove smaller: While the back of dq holds an index whose value is <= nums[i], pop from the back. These elements can never be a window max because nums[i] is larger and will stay in the window longer. c. Push: Append i to the back of the deque. d. Record: If i >= k - 1 (the first full window is formed), append nums[dq[0]] to the result.
3. Return the result array.

Worked Walk-through

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

Why the deque stays monotonic

Whenever we push index i, we first remove all back elements with value <= nums[i]. This guarantees the deque is always in strictly decreasing order of values. The front is the largest, so reading the max is O(1).

Edge Cases

• k = 1: Every element is its own window max. The deque has at most 1 element.
• k = n: One window covering the entire array. Return [max(nums)].
• Decreasing array: The deque grows to size k and the front expires one at a time.

Complexity

• Time: O(n) — each index is pushed and popped from the deque at most once.
• Space: O(k) — the deque holds at most k indices.