Maintain Sliding-Window Maximums

Practice Exercise Intermediate Medium Monotonic Queue Array Deque

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement window_maximums(values, window_size). Assume 1 <= window_size <= len(values). Return the maximum of every contiguous window.

Starter code

def window_maximums(values, window_size):
    pass

Test cases

mixed-windows

{
  "args": [
    [
      1,
      3,
      -1,
      -3,
      5,
      3,
      6,
      7
    ],
    3
  ]
}

Expected: [3,3,5,5,6,7]

single-width

{
  "args": [
    [
      4,
      2,
      9
    ],
    1
  ]
}

Expected: [4,2,9]

Wizard outline

Step 1: Keep decreasing candidates
Return the first window maximum from a monotone deque. Any smaller value behind the current value can never win a future overlapping window.
Step 2: Expire the old front
Slide distinct-value windows without retaining stale candidates. Only indexes greater than index - window_size remain inside the current window; duplicate replacement is deferred to the next checkpoint.
Step 3: Resolve duplicate candidates
Complete the contract for equal maxima and all window sizes. Replacing equal older indexes with the newer one delays expiry without changing the maximum.

Footguns and prerequisites

Storing only values makes duplicate expiry ambiguous.
Removing expired indexes after reading the maximum can emit stale results.
arrays strings two pointers sliding window

Reviewed references

Python collections.deque

Recommended approach and implementation

Maintain a deque of in-window indexes whose values decrease from front to back.

Why it works: Expired indexes are removed before output. Every dominated suffix is removed because the newer value is at least as large and lasts longer; therefore the front is always the current window maximum.

from collections import deque

def window_maximums(values, window_size):
    candidates = deque()
    results = []
    for index, value in enumerate(values):
        while candidates and candidates[0] <= index - window_size:
            candidates.popleft()
        while candidates and values[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(index)
        if index >= window_size - 1:
            results.append(values[candidates[0]])
    return results