901. Online Stock Span

901

MediumMonotonic Stack and Monotonic QueueMonotonic decreasing stack storing (price, span) pairsPrevious-greater span via monotonic stack

Online Stock Span

Design a StockSpanner that receives the day's stock price via successive next(price) calls. For each call, return the stock's span: the number of consecutive days ending today (including today) on which the price was less than or equal to today's price.

Open official problem prompt ↗

In plain English

For each incoming price, report how many consecutive prior days (up to and including today) had a price at or below today's, using only past data as it streams in.

Picture it like this

Think of stacking plates of increasing height from the back. When a tall plate arrives, it hides all the shorter-or-equal plates in front of it, so it 'inherits' their combined coverage; only a taller plate behind it can block the view.

Example

Input: next(100), next(80), next(60), next(70), next(60), next(75), next(85)
Output: [1, 1, 1, 2, 1, 4, 6]
Why: When 75 arrives it covers 60, 70, and 60 plus itself for a span of 4; 85 then covers 75, 60, 70, 60 plus itself for a span of 6, stopping at 100.

Constraints

1 <= price <= 10^5At most 10^4 calls to nextPrices arrive one at a time (online / streaming)

Pattern lesson

See the pattern, then code

Previous-greater span via monotonic stack

↗

Monotonic Stack and Monotonic Queue

Next greater or smaller value, nearest boundary, histogram, or window extremum.. Instead of rescanning history, keep a decreasing stack of (price, span) pairs. A new price swallows every stacked price it meets or exceeds, absorbing their spans, so each day is pushed and popped at most once for amortized O(1) work.

New words, made simpleKnow these before the algorithm

Span: Count of consecutive days ending today whose price is <= today's price.
Online algorithm: Processes each input as it arrives without seeing future values.
Amortized O(1): Each element is pushed and popped once total, so the average cost per call is constant even though a single call may pop many items.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Rescan history each call

Repeatedly re-examines the same days; too slow over many calls.

On every next(price) walk backward counting days with price <= current.

Time O(n) per call, O(n^2) totalSpace O(n)

Best choiceMonotonic stack of (price, span)

Each day is touched a constant number of times, giving linear total work.

Collapse consumed days into the current day by absorbing their spans, keeping a decreasing stack.

Time O(1) amortized per callSpace O(n)

The rule we keep true

Invariant

After each call the stack's prices are strictly decreasing from bottom to top, and each stored span equals the full run that element already summarizes.

Why this is correct

Reasoning

When a new price pops an earlier price p <= price, every day p was summarizing is also <= the new price (since p was at least as large as all of them), so its span can be folded into the current span. Popping stops at the first strictly greater price, which correctly bounds the run. Because a day, once popped, is folded into a survivor and never revisited, total pops are bounded by total pushes — hence amortized O(1).

The algorithm in three movesSay these aloud before coding

1Store a stack of (price, span) pairs, initially empty

before 75: stack=[(100,1),(80,1),(70,2),(60,1)]

2On next(price), start span = 1

75 pops (60,1),(70,2) -> span=1+1+2=4

3While the stack top's price <= price, pop it and add its span to the current span

85 pops (75,4),(80,1) -> span=1+4+1=6, stops at 100

4Push (price, span) and return span

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1000

801

602

703

604

755

856

1 · Readprice=100

2 · AskTop <= 100?

3 · Update statestack empty

4 · Resultspan=1; push (100,1) -> 1

Key takeaway

Each new price absorbs the spans of all earlier prices it meets or exceeds, until a strictly greater price blocks it.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 1-3Stack of price/span pairs
Each entry remembers a price and how many days it already accounts for.
2
Lines 6Today counts as 1
The span starts at 1 for the current day before absorbing earlier days.
3
Lines 7-8Absorb smaller-or-equal days
Popping while the top price is <= today folds their spans in, collapsing the run in one step.
4
Lines 9-10Record and return
Push the merged (price, span) so future days can absorb it in turn, then return the span.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

First call always returns 1
A strictly decreasing price stream returns all 1s
A strictly increasing stream makes each span grow by one
Equal consecutive prices are absorbed because the comparison is <=

Common beginner mistakes

Using < instead of <= fails to count earlier days that equal today's price
Storing only prices loses the span information needed to collapse runs
Rescanning the stack without popping reduces to the quadratic approach
Resetting the stack between calls breaks the online nature of the problem

Check your understanding

Why can we discard the individual days once they are absorbed into a survivor's span?

Online Stock Span

Online Stock Span

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Monotonic Stack and Monotonic Queue