The problem
Return the maximum of every contiguous window of size k as it slides across the array.
Stuck? Reveal hints one at a time
How to approach it
- 1For each index i: pop the back of the deque while its value ≤ nums[i] (dominated forever).
- 2Push i on the back.
- 3Pop the front if it slid out of the window (front ≤ i − k).
- 4Once i ≥ k − 1, record nums[front] as the window max.
Key insight
The deque stores exactly the elements that could still become a maximum — every index enters and leaves at most once, so the whole scan is O(n).
The solution
Watch out for
- Store indices — you need them to know when the front expires.
- Evict with ≤ (not <) from the back so duplicates don’t pile up.