Sliding Window Maximum in Java: Solution, Explanation & Practice

Find maximum in each sliding window

Problem summary

Given an array and window size k, find the maximum in each window position.

Starter code

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        
        // Find max in each window of size k
        // Print maximums space-separated
    }
}

Expected output and test cases

Window size 3
```
3 3 5 5 6 7
```
Window size 4
```
5 5 6 7 7
```
Window size 1
```
1 3 -1 -3 5 3 6 7
```

Hints

Use Deque for efficient O(n)
Store indices, not values
Remove elements outside window

Validated solution

Reveal Java solution

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

public class Main {
    static int[] maximums(int[] values, int k) {
        int[] answer = new int[values.length - k + 1];
        Deque<Integer> candidates = new ArrayDeque<>();
        for (int i = 0; i < values.length; i++) {
            while (!candidates.isEmpty() && candidates.peekFirst() <= i - k) candidates.removeFirst();
            while (!candidates.isEmpty() && values[candidates.peekLast()] <= values[i]) candidates.removeLast();
            candidates.addLast(i);
            if (i >= k - 1) answer[i - k + 1] = values[candidates.peekFirst()];
        }
        return answer;
    }
    public static void main(String[] args) {
        for (int value : maximums(new int[] {1, 3, -1, -3, 5, 3, 6, 7}, 3)) System.out.print(value + " ");
    }
}

How to approach the problem

The deque stores indices whose values could still become a window maximum, in decreasing-value order. Remove expired indices from the front and weaker values from the back; the front then names the current maximum.

Approach

Reject k outside 1 through array length in production code.
Discard indices outside the left window edge.
Discard smaller trailing candidates before adding the new index.

Time and space complexity

Time: O(n). Space: O(k).

Edge cases to test

k = 1 returns every input value.
Equal values can keep only the newer index because it will expire later.

Common mistakes

Storing values rather than indices and being unable to detect expiration.
Recomputing each window’s maximum from scratch.

Follow-up challenge

Calculate sliding-window minima with the same deque pattern.

Related Collections exercises

Practice all Collections exercises · Run this idea in the Java compiler