Java sliding-window maximum: evict expired indices and weaker tails

Last updated: 30 Sept 20264 min read

tutorial

A deque of candidate indices can report the maximum of every fixed-width window in one pass.

Keep only useful candidates

Before adding an index, remove a head that has left the current window. Then remove tail indices whose values are no greater than the incoming value: the new index lasts longer and is at least as strong. The head is the maximum for the current window.

The fixture uses width three and checks that width one returns the original values. Empty input, zero width and width above input length are rejected in this API. Next greater elements share the monotonic idea but answer a different query.

Tie behavior is deliberate

Using <= discards older equal values. That is safe for maximum values; if the product needs the earliest index among equal maxima, use a different tie rule and test it. A deque stores indices so expiry is cheap.

Working program

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class PeakReviewWindow {
    static int[] maxima(int[] load, int width) {
        if (width < 1 || width > load.length) throw new IllegalArgumentException("width");
        int[] answer = new int[load.length - width + 1];
        Deque<Integer> candidates = new ArrayDeque<>();
        for (int index = 0; index < load.length; index++) {
            while (!candidates.isEmpty() && candidates.peekFirst() <= index - width)
                candidates.removeFirst();
            while (!candidates.isEmpty() && load[candidates.peekLast()] <= load[index])
                candidates.removeLast();
            candidates.addLast(index);
            if (index + 1 >= width) answer[index - width + 1] = load[candidates.peekFirst()];
        }
        return answer;
    }
    public static void main(String[] args) {
        int[] load = {2, 5, 1, 4, 6, 3};
        System.out.println(Arrays.toString(maxima(load, 3)));
        if (!Arrays.equals(maxima(load, 1), load)) throw new AssertionError("width one");
    }
}

Output

[5, 5, 6, 6]

Costs and boundaries

Each index enters and leaves the deque at most once: O(n) time, O(width) candidate space and O(n-width+1) output space. This is for one fixed width, not arbitrary range maximum queries.

Common Mistakes

Do not leave an expired head in the deque.
Do not assume a tie policy if the answer needs an index rather than a value.
Do not accept width zero or greater than the input length without an explicit contract.