AI Hints
Home›DSA in Python Tutorial›Windows, Words and Networks
DSA in Python · Lesson 115 of 132

Practice: Sliding Window Maximum

A deque of candidates.

⏱ 2 min read▶ Video at 2:17:10🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Slide a window of size K across a list, and report the largest number in every window. Checking every window from scratch costs O of N times K. We can do it in O of N, with a deque.

Practice: Sliding Window Maximum
From the video: Practice: Sliding Window Maximum
  • A window of size k
  • The max of every window
  • O(n) with a deque

Keep only useful candidates

The deque holds positions, with their values in decreasing order. When a new number arrives, any smaller numbers behind it can never be the maximum again, so we pop them. If the front has slid out of the window, we drop it. The front is always the window's maximum. Run it.

window_max.pypython
from collections import deque

def window_max(nums, k):
    q, out = deque(), []
    for i, x in enumerate(nums):
        while q and nums[q[-1]] <= x:
            q.pop()
        q.append(i)
        if q[0] <= i - k:
            q.popleft()
        if i >= k - 1:
            out.append(nums[q[0]])
    return out

print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
Output
[3, 3, 5, 5, 6, 7]

A monotonic deque

A deque kept in sorted order like this is called a monotonic queue. Each position is added once and removed at most once, so the whole thing is O of N, even with the inner while loop. The same idea finds the next greater element, and daily temperatures.

keyvalue
Deque holdspositions, values decreasing
New numberpops smaller ones
Frontthe window max
CostO(n)

Summary

Keep a deque of candidates in decreasing order, and the front is always the maximum. Each item enters and leaves once. Next, splitting a string into words.

Key takeaways
  • Pop smaller from the back
  • Drop old from the front
  • Front is the max
Next up: Practice: Word Break — dynamic programming on strings