Sliding Window Maximum

Step 1: Why a running value is not enough

For a sum, we add what enters and subtract what leaves. A maximum cannot be "subtracted": when the current maximum leaves the window, we need the next largest, and finding it by scanning the window costs O(k) per step.

Step 2: Some elements can never be the answer

Suppose nums[i] arrives and an earlier element in the window is smaller or equal. That earlier element will leave the window before nums[i], and while both are present, nums[i] is at least as large. So the earlier one can never be a window maximum again, and can be thrown away.

Step 3: A deque of candidates

Keep the indices of the remaining candidates in a deque. After throwing away the useless ones, their values are in decreasing order from front to back. For each new index i:

• if the front index has left the window (it is i - k or older), remove it from the front;
• remove indices from the back while their values are at most nums[i];
• add i at the back;
• once the first window is complete, the front is the maximum.

The deque holds indices, not values, so we can tell when an element has left the window.

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. The deque is shown by value.

ArrayDeque gives O(1) access to both ends, which is all a monotonic deque needs.

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

public class SlidingWindowMaximum {

    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();   // indices; their values decrease front to back
        for (int i = 0; i < nums.length; i++) {
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();               // the front index has left the window
            }
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();                // smaller values can never be a maximum again
            }
            dq.offerLast(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];   // the front is the maximum
            }
        }
        return result;
    }

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

The original implementation, SlidingWindowMaximum.java, is on GitHub.

• Time: O(n): every index is added to the deque once and removed at most once.
• Space: O(k) for the deque.

A max-heap with lazy removal also works in O(n log n). For the median of each window, see Sliding Window Median.