Hard · Monotonic Deque
Understand → Visualise → Practice.
A deque (double-ended queue) lets you add and remove at both ends in O(1). That makes it ideal for window maximums.
Keep indices in the deque with decreasing values. Remove smaller values from the back before adding, and drop the front when it leaves the window.
Pop while the back value ≤ the new value.
Pop the front if it is outside the window.
Once the window is full, the front is the answer.
O(n) time, O(k) space. A heap would take O(n log n).
Store indices, not values, so you can tell when the front has left the window.
Read the full guides first: Stacks, Queues and Deques.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.