Maximum of every sliding window

Question

Given a price series and window length k, output the maximum of every contiguous window of k prices, the rolling high a market-data system publishes on every tick. Return all window maxima in O(n) total. Recomputing each window's max is O(nk); a heap gets O(n \log n) with fiddly stale-entry cleanup. The target is the monotonic deque.

Accepted Answer

Key observation: once a newer, higher price exists, every older lower price is permanently dominated, it can never be the max of any future window, because any window containing it also contains the newer higher price. So we only need to remember the prices that are not yet dominated: a decreasing sequence, stored as indices in a deque. Per tick: (1) pop from the back every index whose price is at most the new price (they're now dominated); (2) push the new index; (3) pop the front if it has slid out of the window; (4) the front is the window max. Tracing the example: when 5 arrives it evicts…

Maximum of every sliding window

Your answer

More Coding questions