Sliding Window Maximum

Hard
Code
Loading editor...
Tap Analyze to see visualization
Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Sliding Window Maximum

Approach

Use an array as a monotonic deque storing indices in decreasing order of their values. For each new element, remove indices from the back that have smaller values (they can never be the max), and remove indices from the front that are outside the window. The front of the deque is always the index of the current window maximum.

Complexity Analysis

Time
O(n)
Space
O(k)

Pattern

Sliding Window (Monotonic Deque)

Why It Works

Each index is pushed and popped at most once across the entire traversal, giving amortized O(1) per element. The decreasing invariant ensures the front is always the maximum. Removing out-of-window indices from the front keeps only valid candidates.

Updated Feb 2026