Days until a higher price

Question

Given a series of daily prices, for each day report how many days you must wait until a strictly higher price appears. If no higher price ever comes, report 0. Return the wait array in O(n).

Accepted Answer

Maintain a stack of indices whose prices are strictly decreasing: these are days still looking for a higher future price. When a new price arrives, it settles every stacked day it exceeds. The wait for a settled day is the gap between today and that day. Tracing [73, 74, 75, 71, 69, 72, 76, 73]: the 75 on day 2 waits until the 76 on day 6, a gap of 4; the final two days never see anything higher, so they get 0. Result: [1, 1, 4, 2, 1, 1, 0, 0]. Each index is pushed once and popped at most once, so the total work is O(n). Space O(n) for the stack in the worst case (a strictly decreasing series…

Days until a higher price

Your answer

More Coding questions