Online Stock Span

Q: How do you solve Online Stock Span?

Maintain a monotonic decreasing stack where each element is a tuple of (price, span). For each new price, initialize span=1, then pop from the stack while the top price is less than or equal to the current price, adding the popped spans to span. Push the current (price, span) onto the stack and return span. This approach guarantees amortized O(1) time per next() call.

Q: What is the time complexity of Online Stock Span?

O(n). Each price is pushed and popped at most once from the stack, so the total operations over n calls to next() is O(n), resulting in amortized O(1) time per call.

Q: What pattern does Online Stock Span use?

The Pattern: Monotonic Decreasing Stack (Compress Consecutive Smaller Values) The Heuristic: For each day, all we really care about is how many consecutive earlier days had prices less than or equal to today’s price. We use a monotonic decreasing stack to pop earlier days whose prices are less than or equal to today’s and add their stored spans into today’s span, so only earlier days with higher prices remain on the stack. This way we do not need to walk back through every previous day each time we process a new price, because the stack has already collapsed runs of smaller prices into a single span value.

Medium Monotonic Stack

Problem

Given a stream of daily stock prices, return the span of the stock's price for the current day, where the span is defined as the maximum number of consecutive days (up to today) the price was less than or equal to today's price.

Calls to next() are made sequentially for each day.
1 ≤ price ≤ 10⁵
At most 10⁴ calls to next() will be made.

Example

Input: prices = [100, 80, 60, 70, 60, 75, 85]

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

Day 1: price=100, no previous days, span=1. Day 2: price=80, previous price 100 > 80, span=1. Day 3: price=60, previous prices 80 and 100 > 60, span=1. Day 4: price=70, previous price 60 <= 70, span includes day 3 and 4, span=2. Day 5: price=60, previous price 70 > 60, span=1. Day 6: price=75, previous prices 60 (day 5), 70 (day 4) <= 75, span includes days 3 to 6, span=4. Day 7: price=85, previous prices 75, 70, 60, 80, 100; all except 100 <= 85, span=6.

Approach

Straightforward Solution

A naive approach would check each previous day one by one until a higher price is found, resulting in O(n) time per query and O(n^2) total time for n days, which is inefficient for large inputs.

Core Observation

The span for a given day depends on how many consecutive previous days had prices less than or equal to the current price. This naturally suggests a data structure that can efficiently track and collapse consecutive days with smaller or equal prices.

Path to Optimal

Preview

The key insight is to use a stack that stores pairs of (price, span) in decreasing order of price. When a new price arrives, pop all prices from the stack that are less than or equal to it, accumulating their spans…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Maintain a monotonic decreasing stack where each element is a tuple of (price, span). For each new price, initialize span=1, then pop from the stack while the top price is less than or equal to the current price, adding the popped spans to span…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each price is pushed and popped at most once from the stack, so the total operations over n calls to next() is O(n), resulting in amortized O(1) time per call.

Space

O(n)

In the worst case, the stack stores all prices if they are strictly decreasing, requiring O(n) auxiliary space.

Pattern Spotlight

Monotonic Decreasing Stack (Compress Consecutive Smaller Values)

For each day, all we really care about is how many consecutive earlier days had prices less than or equal to today’s price. We use a monotonic decreasing stack to pop earlier days whose prices are less than or equal to today’s and add their stored spans into today’s span, so only earlier days with higher prices remain on the stack. This way we do not need to walk back through every previous day each time we process a new price, because the stack has already collapsed runs of smaller prices into a single span value.

Solution

Python

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

Step-by-Step Solution

Initialize Monotonic Stack to Store Price and Span Pairs

3	`self.stack = []`

Objective

To create a stack that will hold tuples of (price, span) to efficiently track consecutive days with smaller or equal prices.

Key Insight

Storing both price and its span allows collapsing multiple days into a single stack entry, enabling efficient aggregation of spans when a new price arrives. This data structure is the foundation for the amortized O(1) solution.

Interview Quick-Check

Core Logic

The stack stores pairs of (price, span) in strictly decreasing order of price, enabling efficient span calculation.

Common Pitfalls & Bugs

Forgetting to store the span alongside the price would force repeated counting of consecutive days, losing the amortized efficiency.

Accumulate Span by Popping Smaller or Equal Prices

To compute the span for the current price by collapsing all consecutive previous days with prices less than or equal to it.

Push Current Price and Span, Then Return Span

To record the current price and its computed span on the stack and return the span as the result for this day.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 8 Critical

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

While the stack is not empty and the top price is less than or equal to the current price, pop from the stack.

This loop collapses all consecutive previous days with prices less than or equal to the current price, enabling efficient aggregation of their spans into the current span.

Line 9 Critical

span += self.stack.pop()[1]

Add the popped span to the current span.

Accumulating the spans of popped entries correctly counts all consecutive days dominated by the current price, ensuring the span reflects the total consecutive days with prices <= current price.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does popping all smaller or equal prices from the stack and accumulating their spans correctly compute the current day's span?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Online Stock Span from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Online Stock Span drill

or drill a free problem

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