239. Sliding Window Maximum

NeetCode: Sliding Window Maximum · LeetCode: 239. Sliding Window Maximum · Difficulty: Hard

Given an int[] nums and a window size k, return the maximum of every contiguous window of length k as it slides from left to right.

Example

Input:  nums = [1, 2, 1, 0, 4, 2, 6], k = 3    Output: [2, 2, 4, 4, 6]

Brute force: scan each window

import java.util.Arrays;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < result.length; 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;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.maxSlidingWindow(new int[] {1, 2, 1, 0, 4, 2, 6}, 3)));
        System.out.println(Arrays.toString(s.maxSlidingWindow(new int[] {1, -1}, 1)));
    }
}

[2, 2, 4, 4, 6]
[1, -1]

Time: O(n · k). Space: O(1) beyond the output array of n - k + 1 values. LeetCode guarantees 1 <= k <= n.

Optimal: monotonic deque

Keep an ArrayDeque<Integer> of candidate indices, ordered so their values are in decreasing order from front to back. The front is always the maximum of the current window. This works because if a new number is bigger than some older candidate, that older one can never be the maximum again (the new one is later, so it stays in the window longer), so drop it.

• Before pushing index i, pop from the back every index whose value is <= nums[i].
• Push i.
• Pop from the front if it has fallen out of the window (front + k <= i). The deque is never empty at this point, because i was just pushed.
• peekFirst and peekLast return the ends without removing them, and pollFirst and pollLast remove them.
• Once i + 1 >= k, the front is the answer for this window.

Trace for [1, 2, 1, 0, 4, 2, 6], k = 3 (deque shows values):

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

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>(); // indices, values decreasing
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            deque.addLast(i);
            if (deque.peekFirst() + k <= i) {
                deque.pollFirst(); // left the window
            }
            if (i + 1 >= k) {
                result[i + 1 - k] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.maxSlidingWindow(new int[] {1, 2, 1, 0, 4, 2, 6}, 3)));
        System.out.println(Arrays.toString(s.maxSlidingWindow(new int[] {1, -1}, 1)));
    }
}

[2, 2, 4, 4, 6]
[1, -1]

Time: O(n): each index is pushed and popped at most once. Space: O(k).

How to explain it in an interview

• Say first: scan each window for its max, O(n · k).
• Key insight: keep only candidates for "maximum of some future window" in decreasing order; smaller older values are useless once a bigger newer one arrives.
• Code it in steps: (1) ArrayDeque of indices; (2) pollLast while the back's value is <= nums[i]; (3) addLast(i); (4) pollFirst if it is out of the window; (5) once the first window is full, push nums[front] to the result.
• Complexity to state: O(n) time, O(k) space, because every index enters and leaves the deque once.
• Likely follow-ups / pitfalls: store indices, not values, so the front's expiry can be detected; a heap works too at O(n log n) with lazy deletion.