MediumStackDesignMonotonic StackData Stream

Online Stock Span

1 approach, code in every language

Design an algorithm that computes the span of a stock's daily price as new prices stream in one at a time.

The span of the current day is the number of consecutive days ending with today (including today) for which the price was less than or equal to today's price.

Implement the `StockSpanner` class:

- `StockSpanner()` initializes the object. - `next(price)` records today's `price` and returns the span for that day.

Example 1

Input: StockSpanner(); next(100); next(80); next(60); next(70); next(60); next(75); next(85)

Output: [1, 1, 1, 2, 1, 4, 6]

70 covers itself and the prior 60 (span 2). 75 covers 60, 70, 60 and itself (span 4). 85 covers all of 80, 60, 70, 60, 75 and itself (span 6).

Example 2

Input: StockSpanner(); next(31); next(41); next(48); next(59); next(26)

Output: [1, 2, 3, 4, 1]

Each rising price extends the run: 41 spans 2, 48 spans 3, 59 spans 4. The drop to 26 resets the span to 1.

Constraints

1 <= price <= 10^5
At most 10^4 calls will be made to next.

Decreasing Monotonic Stack of (price, span)

Keep a stack of price/span pairs in strictly decreasing price order; each new price absorbs the spans of all cheaper-or-equal prices beneath it.

Loading animation…

Intuition

When a new price arrives, every recent day whose price was less than or equal to it is already summarized by the span stored on the stack, so we can collapse them in one step instead of rescanning. Pop each pair whose price is at most the new price, adding its span to a running total that starts at 1 for today. The pair now sitting on top is the first strictly higher price, which bounds the run. Push the new price paired with the accumulated span so future days can reuse it. Because each price is pushed and popped at most once, the amortized cost per call is constant.

Algorithm walkthrough

1Store an empty stack of (price, span) pairs in the constructor.
2On next(price), start span at 1 to count today.
3While the stack is non-empty and the top pair's price is less than or equal to price, pop it and add its span to the running total.
4Push the pair (price, span) so it represents this collapsed run.
5Return span, which is the number of consecutive days up to and including today with price at most today's price.

Implementation

class StockSpanner:
    def __init__(self):
        self.stack = []  # list of (price, span)

    def next(self, price: int) -> int:
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

Time

O(1) amortized per next call

Space

O(n)

n is the number of calls. Each price is pushed once and popped once across all calls, so the total work is linear.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free