Sliding Window Maximum

Given an array and window size k, return the maximum in every window [i, i+k-1]. A monotonic deque (double-ended queue) that keeps indices of elements in decreasing value order gives O(n) time.

Idea

  • The deque stores indices such that their values are in decreasing order (front = index of current window max).
  • When the window moves:
    • Remove indices that have left the window (front index < left bound of window).
    • Before adding the new index right, remove from the back all indices whose values are ≤ nums[right] (they can never be the max for any future window containing right).
    • The front is the index of the maximum in the current window.

Implementation

Java
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

    for (int i = 0; i < n; i++) {
        while (!dq.isEmpty() && dq.peekFirst() < i - k + 1)
            dq.pollFirst();
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i])
            dq.pollLast();
        dq.offerLast(i);
        if (i >= k - 1)
            result[i - k + 1] = nums[dq.peekFirst()];
    }
    return result;
}

Why O(n)

Each index is pushed once and popped at most once, so total operations are O(n).

Summary

Sliding window maximum: maintain a monotonic deque (indices, values decreasing). Drop indices outside the window from the front; drop indices with value ≤ new element from the back. Front always gives the current window max.