Stock span with a monotonic stack

Question

The "stock span" on a day is the number of consecutive days ending today (today included) on which the price was less than or equal to today's price.

prices = [100, 80, 60, 70, 60, 75, 85]
-> [1, 1, 1, 2, 1, 4, 6]

Return the span for every day. Aim for $O(n)$ ; the day-by-day backward scan is $O(n^2)$ .

Accepted Answer

Keep a stack of earlier indices whose price is still strictly greater than everything after them, so the stack's prices are strictly decreasing from bottom to top. For a new price p, pop every index whose price is \le p (they are inside today's span). Whatever remains on top is the first taller day to the left; the span is the distance to it. Each index is pushed once and popped at most once, so the total work is linear despite a single day sometimes popping many, the standard amortized argument. Tracing [100, 80, 60, 70, 60, 75, 85]: 100,80,60 each start a fresh span of 1; 70 pops 60, leavin…

Stock span with a monotonic stack

Your answer

More Coding questions