# Monotonic Deques — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/w-deque

> Window maximums in linear time.

## Keep only useful candidates

For the maximum of every window of size k, keep a **deque of indices whose values decrease**. A new element removes smaller values from the back (they can never be the maximum again), the front is dropped when it leaves the window, and the front is always the current maximum. Each index is pushed and popped once: O(n) instead of O(n·k).

## Sliding window maximum, run

I ran this with Python 3.12.3 (standard library only). Window maximums for k = 3 and for a decreasing array with k = 2.

```python
# Sliding window maximum with a monotonic deque: O(n)
from collections import deque

def window_max(nums, k):
    dq, out = deque(), []                # indices, values decreasing
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                     # smaller values can never be a max again
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()                 # drop index that left the window
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(window_max([9, 8, 7, 6], 2))
```

Output:

```
[3, 3, 5, 5, 6, 7]
[9, 8, 7]
```

## Store indices, not values

Indices let you tell when the front has left the window.

**Quiz:** Why can smaller values be removed from the back of the deque?

- [ ] The deque has a size limit
- [ ] They are duplicates
- [x] A newer, larger value will outlast them in every future window
- [ ] They are negative

*Answer:* A newer, larger value will outlast them in every future window. They can never be the maximum.