☕ DSA Java Articles

Topics › Stacks and Queues › Implementation Problems

Sliding Window Maximum

Hard TUF ID 963 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an integer array nums and a window size k. A window of k consecutive elements starts at the left end and slides one position to the right at a time until it reaches the right end. Return an array with the maximum of each window, in order. There are n - k + 1 windows.

Constraints: 1 ≤ k ≤ n ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4. The Java file returns an empty array for an empty input or an invalid k.

Example 1

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

Example 2

nums = [9, 8, 7, 6], k = 2
answer = [9, 8, 7]       // each window's maximum is its first element

Approach 1: Brute force

Intuition. Compute every window’s maximum from scratch with an inner loop. Each window shares k - 1 elements with the previous one, so most of that work is repeated, but it is the obvious correct baseline.

Algorithm.

  1. For every start i from 0 to n - k:
  2. Scan nums[i..i+k-1] for the maximum and store it in res[i].
static int[] bruteForce(int[] nums, int k) {
    int n = nums.length;
    if (n == 0 || k <= 0 || k > n) return new int[0];
    int[] res = new int[n - k + 1];
    for (int i = 0; i + k <= n; i++) {
        int mx = Integer.MIN_VALUE;
        for (int j = i; j < i + k; j++) mx = Math.max(mx, nums[j]);
        res[i] = mx;
    }
    return res;
}

Complexity. Time O(n · k): n - k + 1 windows, k elements each. In the worst case (k ≈ n/2) this is quadratic, about 2.5 × 10^9 steps for n = 10^5. Space O(1) besides the output.

Approach 2: Better, a max-heap with lazy deletion

Intuition. A max-heap gives the largest element in O(1) and accepts new elements in O(log n). The problem is removal: when the window slides, the element that leaves might be buried anywhere in the heap, and Java’s PriorityQueue.remove(Object) is linear.

The trick is to not remove it right away. Store {value, index} pairs. When we need the maximum of the window ending at i, look at the top of the heap; if its index is ≤ i - k, it has already left the window, so discard it and look again. Elements that left the window but are not on top do no harm: they can never be reported unless they reach the top, and then they are discarded.

Algorithm.

  1. For each i, push {nums[i], i}.
  2. Once the first full window exists (i ≥ k - 1): pop while the top’s index is ≤ i - k, then record the top’s value as res[i - k + 1].
static int[] better(int[] nums, int k) {
    int n = nums.length;
    if (n == 0 || k <= 0 || k > n) return new int[0];
    int[] res = new int[n - k + 1];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));   // largest value first
    for (int i = 0; i < n; i++) {
        pq.offer(new int[]{nums[i], i});
        if (i >= k - 1) {
            while (pq.peek()[1] <= i - k) pq.poll();      // discard maxima that are no longer in the window
            res[i - k + 1] = pq.peek()[0];
        }
    }
    return res;
}

Complexity. Time O(n log n): each element is pushed once and popped at most once, O(log n) each. The heap can hold up to n entries because stale ones linger (an increasing array never pops anything), so space is O(n).

Approach 3: Optimal, monotonic deque

Intuition. Ask which elements of the current window could ever be a window maximum again, now or in the future.

Suppose j < i, both are in the window, and nums[j] ≤ nums[i]. Every future window that contains j also contains i, because i is to the right and leaves later. In all of those windows nums[i] is at least as large. So j can never again be the answer, and we can throw it away for good.

After discarding all such elements, the survivors have strictly decreasing values from oldest to newest. Store their indices in a double-ended queue:

Algorithm.

  1. For each i:
    • If the front index is ≤ i - k, pop it from the front.
    • While the back value is ≤ nums[i], pop from the back.
    • Push i at the back.
    • If i ≥ k - 1, record nums[front].
static int[] optimal(int[] nums, int k) {
    int n = nums.length;
    if (n == 0 || k <= 0 || k > n) return new int[0];
    int[] res = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();     // front slid out of the window
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();   // can never be a maximum again
        dq.offerLast(i);
        if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
    }
    return res;
}

Dry run on nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 (the deque is shown as values, front first):

i nums[i] expired at front dominated at back deque after output
0 1 none none [1]  
1 3 none 1 [3]  
2 -1 none none [3, -1] 3
3 -3 none none [3, -1, -3] 3
4 5 3 (index 1) -3, -1 [5] 5
5 3 none none [5, 3] 5
6 6 none 3, 5 [6] 6
7 7 none 6 [7] 7

Complexity. Time O(n): every index enters the deque once and leaves at most once, from either end, so the inner while loop runs at most n times in total. Space O(k): the deque only holds indices from the current window.

Popping equal values (≤ rather than <) is a choice, not a requirement. Keeping equal values also works, because the front check uses indices. Popping them keeps the deque smaller.

Edge cases and pitfalls