Sliding Window Maximum

LeetCode 239 • Hard • Sliding Window

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 → Output: [3,3,5,5,6,7]. Monotonic deque: indices in decreasing order. Front = max. O(n).

TimeO(n)

SpaceO(k)

i: — deque: [] result: []

Window

Deque (indices)

Max (front)

i—

deque[]

result[]

Speed:

Ready

Press Play. Monotonic deque: pop from back while nums[back] < nums[i]. Pop front when out of window. Front = max.

Whiteboard

Size:3

Type It

Practice until you don't need to look. Monotonic deque keeps indices in decreasing value order.

═══ SLIDING WINDOW MAXIMUM — MONOTONIC DEQUE ═══

PATTERN ▸ Deque (indices, decreasing) O(n) · O(k)

① INIT

deque, result = [], []

② FOR i IN RANGE(n)

while deque and nums[deque[-1]] < nums[i]: deque.pop()

deque.append(i)

if deque[0] <= i - k: deque.popleft()

if i >= k - 1: result.append(nums[deque[0]])

③ RETURN

return result

your implementation

Verify: