← Queue Patterns

Micro-Drill #43 — Sliding window max setup

Queue Patterns Target: 15s

Monotonic deque maintains window max in O(n). Used for sliding-window-maximum and similar.

from collections import deque
dq = deque()  # indices
for i, x in enumerate(a):
    while dq and dq[0] < i - k + 1:
        dq.popleft()
    while dq and a[dq[-1]] <= x:
        dq.pop()
    dq.append(i)
    if i >= k - 1:
        result.append(a[dq[0]])

Type it from memory. Go.

Practice Problems

• 239. Sliding Window Maximum
• 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Related Coding Drills

• Drill #106 — Sliding Window Maximum Hard
• Drill #7 — Sliding window max sum of k elements Easy
• Drill #105 — Minimum Window Substring Hard