LeetCode 239 · Sliding Window

Sliding Window Maximum, explained with a picture

The tallest tower in view from a train.

HardSliding Window
▶ Watch it step by step

The problem

Given a list of numbers and a window size k, slide the window from left to right one step at a time and report the largest number in each window.

Input:  [1, 3, 1, 2, 1, 5, 3, 6, 7], k = 3
Output: [3, 3, 2, 5, 5, 6, 7]

Picture it

Picture riding a train and seeing k towers through the window at once. You keep a short list of candidates, tallest first. When a new tower appears, any shorter towers in the list are now useless (the new one is taller and will stay in view longer), so they are thrown out. The front of the list is always the tallest in view; if it has slid out of the window, drop it.

How to recognise it

  • A window of fixed size k slides one step at a time, and you need the maximum (or minimum) of each window.
  • A plain running maximum fails, because the maximum can leave the window, and then you need the next-best value at once.
  • Smaller values that arrive before a bigger one can never be the maximum again while that bigger one is in the window. That is the hint for a structure that throws them away.
  • n is up to 10^5 and k can be as large as n, so recomputing each window is too slow.

Start with brute force

Take the maximum of every window directly.

def max_window_brute(h, k):
    return [max(h[i:i + k]) for i in range(len(h) - k + 1)]

There are n − k + 1 windows, each costing O(k), so time is O(n · k). The worst case is k around n/2: with n = 10^5 that is about 2.5 × 10^9 steps. Space is O(k) for each slice.

From brute force to the idea

  1. Find the waste. Neighbouring windows share k − 1 values, but each maximum is recomputed from scratch.
  2. Drop values that can never win. When x arrives, any earlier value that is no bigger than x is useless: x is at least as big and will stay in the window longer. Pop those from the back.
  3. Keep a decreasing queue. After the pops, the values in the deque are in decreasing order from front to back, so the front is the maximum of the window.
  4. Store positions, not values. The deque holds indices, so you can tell when the front has slid out: if dq[0] <= i - k, it is no longer in the window, so pop it from the front. Only the front can be out of date, because the deque is in order of position.
  5. Report once the window is full. From i = k - 1 onwards, append h[dq[0]].

This is the key idea: a deque of positions with decreasing values, where the front is always the current maximum.

The key idea

A deque kept in decreasing order: the front is always the maximum. Each tower is added and removed at most once: O(n).

Python solution

def max_window(h, k):
    dq, out = deque(), []      # positions, tallest at front
    for i, x in enumerate(h):
        while dq and h[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(h[dq[0]])
    return out

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n · k): every window is scannedO(k): one slice at a time, besides the output
Monotonic deque (shown code)O(n): each index is pushed once and popped at most onceO(k): the deque holds at most k positions, besides the output

The inner while can pop many items on one step, but there are only n pushes, so all pops together total at most n.

Edge cases

  • k = 1 ([4, 2]): returns the list itself, [4, 2].
  • k equals the length ([4, 2, 5], k = 3): returns one maximum, [5].
  • Falling values ([5, 4, 3, 2, 1], k = 3): nothing is popped from the back, the deque grows to k, and old fronts expire: [5, 4, 3].
  • Equal values ([2, 2, 2], k = 2): returns [2, 2]. Because of <=, the older copy is popped, so the deque keeps the newest one, which stays in the window longest.
  • Empty list, or k larger than the list: returns []; no window is ever full.
  • Missing import: the code needs from collections import deque; without it the call raises NameError.

Common mistakes

  • Storing values instead of positions, so you cannot tell when the front has left the window.
  • Expiring with dq[0] < i - k, one step late. The window is then k + 1 wide: [3, 1, 1, 1] with k = 2 returns [3, 3, 1] instead of [3, 1, 1].
  • Using a max-heap without removing expired entries, which reports a value that has already left the window.
  • Worrying about < versus <= in the back pops. Both give correct answers; <= just keeps the deque smaller when values repeat.
Your turn: the spread of each window

For each window of size k, report the maximum minus the minimum. For [1, 3, 1, 2, 1, 5, 3, 6, 7] with k = 3 the answer is [2, 2, 1, 4, 4, 3, 4]. Describe your approach, then write it if you like.

Compare with our answer

Run two deques side by side: one decreasing (front is the maximum), and one increasing (front is the minimum), which pops from the back while the back is at least the new value. Expire both fronts in the same way.

from collections import deque

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

Time O(n), space O(k).

A strong answer mentions: a second deque with the comparison flipped, expiring both fronts, and why it is still O(n).

Check what stuck

1. For each day you must report the lowest price over the last 30 days. Which approach fits best?

2. Why is the shown code O(n) even though a while loop sits inside the for loop?

3. A learner writes if dq[0] < i - k: to expire the front. Which call now returns a wrong answer?

Score 60% or more and the lesson is marked complete.