Python sliding-window maximum: retain only useful deque indexes

Operation contract

The queue drops indexes outside the current three-sample window and removes smaller or equal trailing candidates before appending the new index. Its front is the maximum for each completed window. Keeping indexes, rather than only values, makes expiry unambiguous even when measurements repeat.

Failure and ownership boundary

The function rejects a zero or oversized window and boolean measurements. The deque never needs every historic sample, but the returned output has one value per window. Python sliding window: longest span without repeated symbols, Python Counter and deque: counts, queues and bounded history and Python heapq top-k: define ties before ranking frequencies solve different ordering problems.

Working program

from collections import deque

def window_peaks(samples, width):
    if type(samples) is not list or len(samples) > 100 or any(type(value) is not int for value in samples):
        raise ValueError("bounded integer samples")
    if type(width) is not int or not 1 <= width <= len(samples):
        raise ValueError("window width")
    candidates = deque()
    peaks = []
    for index, value in enumerate(samples):
        while candidates and candidates[0] <= index - width:
            candidates.popleft()
        while candidates and samples[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(index)
        if index + 1 >= width:
            peaks.append(samples[candidates[0]])
    return peaks

print(window_peaks([4, 1, 3, 5, 2], 3))
try:
    window_peaks([4, 1], 0)
except ValueError:
    print("width rejected")

Output

[4, 5, 5]
width rejected

Costs and limits

Each index enters and leaves the deque at most once, giving O(n) time and O(width) candidate storage. Returning all n-width+1 peaks adds O(n) result storage.

Common Mistakes

• Expiring by value cannot distinguish repeated samples.
• A heap needs stale-index handling for this window contract.

Connected lessons

Python sliding window: longest span without repeated symbols, Python Counter and deque: counts, queues and bounded history, Python heapq top-k: define ties before ranking frequencies.