Rolling maximum over a sliding window

Question

For a price series and a window size k, report the maximum price in every window of k consecutive ticks as the window slides one step at a time. Return the list of window maxima. Rescanning each window is O(nk); aim for O(n).

Accepted Answer

Keep a deque of indices whose prices are decreasing from front to back. The front is always the current window's maximum. On each step: drop front indices that have slid out of the window, then pop from the back every index whose price is \le the incoming price (they are dominated and can never win again), then push the new index. Tracing [1,3,-1,-3,5,3,6,7], k=3: window [1,3,-1] max 3; [3,-1,-3] max 3; -1 and -3 get evicted when 5 arrives, giving 5, then 5 again; 6 dominates 3, giving 6; 7 dominates, giving 7. Result [3,3,5,5,6,7]. Each index enters and leaves the deque once, so the work is …

Rolling maximum over a sliding window

Your answer

More Coding questions