Online Stock Span
Online Stock Span: each day a price arrives; return its span — how many consecutive days ending today had price ≤ today's.
- 1 <= price <= 10⁵
- At most 10⁴ calls will be made to next.
Intuition
The online stock span problem streams prices one per day and asks, for each, how many consecutive days ending today had a price less than or equal to today's. The word online matters: you cannot look ahead, and you must answer each day before the next arrives.
Scanning backwards on each call is O(n) per day and O(n²) overall. The way to beat it is to notice which past days can still matter.
Suppose today's price is 80 and yesterday's was 60. Yesterday is swallowed by today's span. And crucially, yesterday can never matter again individually — any future day whose span reaches back past today must also cover yesterday, since today's price is higher. So yesterday's information can be merged into today's and discarded.
That is the compression that makes the algorithm work:
- Keep a stack of (price, span) pairs with strictly decreasing prices; a new price pops and absorbs the span of everything it dominates.
Each new price starts with a span of 1, then repeatedly pops any pair whose price is less than or equal to it, adding that pair's accumulated span to its own. When the popping stops, the remaining top is a higher price that genuinely blocks the span, and the new pair is pushed with its total.
Same monotonic stack, but streaming — you can't look ahead, so instead of resolving pending indices you absorb the ones you dominate. Storing (price, span) pairs lets a popped entry hand over its accumulated count, so spans compress instead of being recounted. That's the trick for any online "how far back does my run extend?" question.
Approach
Before reading on: price up what the direct approach costs here, then ask what ordering you can maintain so the answer is always at one end. Aim for amortized O(1) time and O(n) space.
See why past days can be discarded
If an earlier day's price is at or below today's, any future span reaching past today necessarily covers that earlier day too. It can never be the blocker again, so merging its span into today's loses nothing — this is what makes the stack shrink rather than grow forever.
Store price with accumulated span
The stack holds (price, span) pairs, not bare prices. The span field is what carries the merged history — without it, popping a day would discard the days it had already absorbed.
Start each day at span 1
Today always counts itself, so the span begins at 1 before any popping. This is the base every absorbed span is added to.
Pop and absorb while the top is not greater
While the stack is non-empty and its top price is less than or equal to today's, pop it and add its span to today's. The equal to matters — the problem counts equal prices as part of the span, and using a strict < here silently undercounts on flat runs.
Push the merged pair
After popping stops, push (today's price, accumulated span) and return that span. The stack's prices are still strictly decreasing, since everything at or below today's price was just removed.
Cost across the whole stream
Each day is pushed once and popped at most once, so n calls do O(n) work in total — amortised O(1) per call — even though one individual day can pop many pairs. Space is O(n) in the worst case, when prices arrive in strictly decreasing order and nothing is ever popped.
Solution & live demo
Common pitfalls
Discarding the popped element's span
while self.stack and self.stack[-1][0] <= price:
self.stack.pop()
span += 1while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1]A popped entry stands for a whole run of earlier days it already absorbed, not a single day. Counting it as 1 undercounts every span after the first compression — the accumulated total is exactly why the amortised cost stays O(1).
Using < and mishandling equal prices
while self.stack and self.stack[-1][0] < price:
while self.stack and self.stack[-1][0] <= price:
The span counts days with price less than or equal to today, so an equal earlier price is part of the run and must be absorbed. Strict < leaves it on the stack and reports a span one short.
Edge cases
Every new price pops everything — spans grow like 1,2,3…
≤ comparison absorbs equals into the new span (span counts ≤ days).