Sliding Window Maximum

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

LeetCode: 239. Sliding Window Maximum

Example

Text

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

window              max
[1, 3, -1]           3
[3, -1, -3]          3
[-1, -3, 5]          5
[-3, 5, 3]           5
[5, 3, 6]            6
[3, 6, 7]            7

Output: [3, 3, 5, 5, 6, 7]

There are n - k + 1 windows.

Brute force: scan every window

Java

import java.util.Arrays;

public class Main {
    static int[] windowMax(int[] nums, int k) {
        int[] result = new int[Math.max(0, nums.length - k + 1)];
        for (int start = 0; start + k <= nums.length; start++) {
            int max = nums[start];
            for (int i = start + 1; i < start + k; i++) {
                max = Math.max(max, nums[i]);
            }
            result[start] = max;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(windowMax(new int[] {1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }
}

Output

[3, 3, 5, 5, 6, 7]

Time: O(n · k). Space: O(1) besides the output.

The outer loop visits each window start, and the inner loop reads the k elements of that window. The result array has n - k + 1 entries, or none when k is larger than the array.

Better: a max-heap with lazy removal

Keep the window's elements in a PriorityQueue of {value, index} pairs. PriorityQueue is a min-heap by default, so the comparator Integer.compare(b[0], a[0]) puts the largest value on top. Removing an arbitrary element from a heap is O(n), so elements that have left the window stay in the heap. Before reading the top, poll it while its index is outside the window.

Java

import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
    static int[] windowMax(int[] nums, int k) {
        // each entry is {value, index}; the largest value is on top
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
        int[] result = new int[Math.max(0, nums.length - k + 1)];
        for (int i = 0; i < nums.length; i++) {
            heap.add(new int[] {nums[i], i});
            if (i + 1 >= k) {
                while (heap.peek()[1] + k <= i) {
                    heap.poll(); // index is outside the window i + 1 - k .. i
                }
                result[i + 1 - k] = heap.peek()[0];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(windowMax(new int[] {1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }
}

Output

[3, 3, 5, 5, 6, 7]

Time: O(n log n): every element is pushed and popped at most once. Space: O(n), because stale elements can pile up in the heap.

Optimal: a monotonic deque

Most elements can never be a window maximum. If nums[j] <= nums[i] and j < i, then nums[j] leaves every future window before nums[i] does, and it is never larger. So nums[j] can be discarded as soon as nums[i] arrives.

Keep an ArrayDeque of indices whose values are strictly decreasing from front to back:

Drop from the front an index that has left the window.
Drop from the back every index whose value is <= the new value, then push the new index.
Once the first window is complete, the front holds the index of the window's maximum.

i	nums[i]	deque (values)	max
0	1	1
1	3	3
2	-1	3, -1	3
3	-3	3, -1, -3	3
4	5	5	5
5	3	5, 3	5
6	6	6	6
7	7	7	7

Java

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

public class Main {
    static int[] windowMax(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>(); // indices, values strictly decreasing
        int[] result = new int[Math.max(0, nums.length - k + 1)];
        for (int i = 0; i < nums.length; i++) {
            if (!deque.isEmpty() && deque.peekFirst() + k <= i) {
                deque.pollFirst(); // left the window
            }
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast(); // can never be a maximum again
            }
            deque.addLast(i);
            if (i + 1 >= k) {
                result[i + 1 - k] = nums[deque.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(windowMax(new int[] {1, 3, -1, -3, 5, 3, 6, 7}, 3)));
        System.out.println(Arrays.toString(windowMax(new int[] {9, 8, 7, 6}, 2)) + " "
            + Arrays.toString(windowMax(new int[] {4, 2}, 1)));
    }
}

Output

[3, 3, 5, 5, 6, 7]
[9, 8, 7] [4, 2]

Time: O(n): every index is pushed once and popped at most once. Space: O(k) for the deque.

The window moves by one position per step, so at most one index can expire at a time, and a single if for the front is enough.

Edge cases

k = 1: every element is its own window's maximum.
k equal to the length: one window, the maximum of the whole array.
Decreasing input: nothing is popped from the back, and the front expires on every step.
Sliding window minimum: keep the deque increasing instead (pop from the back while nums[j] >= x).