Online Stock Span

Medium#901price and span

Build a class that gets a stock's price one day at a time. Each call next(price) returns today's span: how many days in a row, counting back from today and including it, the price was not higher than today's. Our example: next(7), next(3), next(4), next(4), next(2), next(9) return 1, 1, 2, 3, 1, 6.

901 Online Stock SpanWalkthrough · 1×

Example: next(7), next(3), next(4), next(4), next(2), next(9). On top are the prices by day; the stack keeps pairs (price, span), and each earlier day belongs to exactly one of them.

012345pricesstackpricespan—
no price yettodaykept in a pair on the stackthe top pair being checkedin today’s span

StockSpanner() is created: init runs once

01/42
restart · back · play · step
Speed
1class StockSpanner:
2 function init():
3 stack = empty stack // pairs (price, span)
4 function next(price):
5 span = 1
6 while stack not empty and top.price <= price:
7 span = span + (pop from stack).span
8 push (price, span) onto stack
9 return span
state
stack
–
price
–
span
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A popped pair is not higher than today, and neither are the days it stands for: they were all at most its price. So today’s span takes in all of them at once.
  2. Pairs on the stack rise towards the bottom: a pair that was not higher would have been popped. The first higher pair ends the span, and nothing under it can be reached.
  3. A popped day is never needed again: today is at least as high and comes later, so any later day either stops at today or goes past both.

Complexity

Each next is O(1) on average: every price is pushed once and popped at most once, so n calls do at most 2n stack steps in all. Memory O(n) for the stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.