Problem Statement

Online Stock Span

Each day a stock price comes in, one at a time. For today's price, we want the "span": how many days in a row, counting today and walking backward, had a price less than or equal to today's price. So if today's price is higher than yesterday's and the day before, those days count, and we stop the moment we hit a day that was more expensive. For prices [100, 80, 60, 70, 60, 75, 85] the spans are [1, 1, 1, 2, 1, 4, 6]. The tool that fits this is a stack. A stack is like a pile of plates: you add a plate to the top and take a plate from the top, so the last plate on is the first one off. Here we keep a special kind of stack called a monotonic stack, which just means the values in it always go in one direction, in our case the prices go from high at the bottom to low at the top. Why a stack fits: when a new, higher price arrives, every smaller price below it is now useless for the future, because that new high price blocks them. So we pop those smaller prices off the top and roll their spans into today's count.

mediumMonotonic StackStackTime: O(n) · Space: O(n)

Signals to notice

calculate span of stock priceconsecutive days with price ≤ todaylook backward efficiently

Brute force first

For each day, scan backward counting — total. Re-scans overlapping portions. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Monotonic decreasing stack of (price, span) pairs. When today's price ≥ stack top, pop and absorb that span. The accumulated span is pushed with today's price. amortized. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `next calls = [100, 80, 60, 70, 60, 75, 85]`

next(100): top none -> span=1; push(100,1); stack=[(100,1)] -> 1
next(80): top 100>80 stop -> span=1; push(80,1); stack=[(100,1),(80,1)] -> 1
next(60): top 80>60 stop -> span=1; push(60,1); stack=[(100,1),(80,1),(60,1)] -> 1
next(70): pop(60,1) span=1+1=2; top 80>70 stop; push(70,2); stack=[(100,1),(80,1),(70,2)] -> 2
next(60): top 70>60 stop -> span=1; push(60,1); stack=[(100,1),(80,1),(70,2),(60,1)] -> 1
next(75): pop(60,1) span=2; pop(70,2) span=4; top 80>75 stop; push(75,4); stack=[(100,1),(80,1),(75,4)] -> 4
next(85): pop(75,4) span=5; pop(80,1) span=6; top 100>85 stop; push(85,6); stack=[(100,1),(85,6)] -> 6

What must stay true

The stack holds prices in decreasing order. When a new price dominates stack entries, their spans are absorbed — they'll never be relevant again because today's price overshadows them. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

function next(price):
  span = 1
  while stack not empty and stack.top.price <= price:
    span += stack.pop().span      # absorb dominated days
  stack.push((price, span))
  return span

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not accumulating spans when popping — each popped entry's span must be added to the current day's span, because those days are now covered by today. The fix is usually to return to the meaning of each move, not just the steps themselves.

Stack Pattern