Sliding Window Maximum

A monotonic deque stores indices whose values decrease front-to-back. The front is always the current window maximum; smaller trailing values are discarded as useless.

Category: Sliding Window
Time complexity: O(n)
Space complexity: O(k)

Pseudocode

maintain a decreasing deque of indices
pop smaller values from the back
drop front if it left the window
front = window maximum

Reference implementation

dq = deque()
for i, v in enumerate(a):
    while dq and a[dq[-1]] &lt; v: dq.pop()
    dq.append(i)
    if dq[0] &lt;= i - k: dq.popleft()
    if i &gt;= k-1: out.append(a[dq[0]])

Open the interactive Sliding Window Maximum visualisation →