Widest price range in a sliding window

Question

You are watching a price tape and want to know how choppy the market gets. For a fixed window length k, the "range" of a window is its highest price minus its lowest price. Scan every window of exactly k consecutive ticks and report the widest range seen.

prices = [3, 1, 4, 1, 5, 9, 2], k = 3
-> 8            # window [1, 5, 9] has range 9 - 1

Return the maximum of (window max - window min) over all length-k windows. Aim for $O(n)$ , recomputing the max and min of each window is $O(nk)$ .

Accepted Answer

Maintain two monotonic deques of indices: one whose prices decrease from front to back (its front is the current window maximum) and one whose prices increase (its front is the minimum). When a new price arrives, pop from the back of each deque any index that can no longer be the extreme, then append the new index. Before reading the extremes, drop the front index if it has slid out of the window. Tracing the example, the window ranges are 3, 3, 4, 8, 7, so the answer is 8. Time O(n), each index is pushed and popped from each deque at most once, and space O(k). Edge cases: k len(prices) produ…

Widest price range in a sliding window

Your answer

More Coding questions