Running minimum over a sliding window

Question

For a price series and window length k, report the minimum price in each window of k consecutive ticks, one value per window. Return the list of window minima. Aim for O(n).

Accepted Answer

Keep a deque of indices whose prices increase from front to back, so the front is always the current window's minimum. When a new price arrives, pop from the back every index whose price is greater than or equal to it, those can never be the minimum again while the newcomer is around. Then evict the front if it has slid out of the window, and once a full window exists, read the front. Tracing [4, 2, 5, 1, 3] with k = 3: the window minima are 2, then 1, then 1, giving [2, 1, 1]. Time O(n), each index is pushed and popped at most once, so the inner while is amortized O(1), and space O(k). Evict…

Running minimum over a sliding window

Your answer

More Coding questions