LeetCode #901 Medium

Online Stock Span

Each day a price arrives; return its span — how many consecutive days ending today had price ≤ today's.

stackmonotonic-stackdesign

02

Intuition

A price swallows the spans of every smaller-or-equal price before it. Keep a stack of (price, span) pairs with strictly decreasing prices: a new price pops and absorbs what it dominates, then pushes its accumulated span.

How to spot this pattern

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.

03

Approach

1

Spans compress history

Once a day is inside some later day's span, it can never matter individually again — safe to merge and discard.

2

Pop while ≤

New price p starts with span 1, adds the span of every popped pair with price ≤ p, then pushes (p, span).

3

Amortized O(1) per day

Each pair pushed once, popped at most once — n calls cost O(n) total.

04

Solution & live demo

▶1class StockSpanner:
▶2    def __init__(self):
▶3        self.stack = []            # (price, span), prices decreasing
▶4 
▶5    def next(self, price):
▶6        span = 1
▶7        while self.stack and self.stack[-1][0] <= price:
▶8            span += self.stack.pop()[1]
▶9        self.stack.append((price, span))
▶10        return span

05

Common pitfalls

Discarding the popped element's span

✗ Wrong

while self.stack and self.stack[-1][0] <= price:
    self.stack.pop()
    span += 1

✓ Right

while 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

✗ Wrong

while self.stack and self.stack[-1][0] < price:

✓ Right

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.

06

Edge cases

Strictly increasing prices

Every new price pops everything — spans grow like 1,2,3…

Equal prices

≤ comparison absorbs equals into the new span (span counts ≤ days).

07

Complexity

Time

amortized O(1)

Space

O(n)

Each price enters/leaves the stack once.