Online Stock Span (LeetCode 901)

The problem

Design a class StockSpanner whose method next(price) is called once per day with that day’s stock price. It returns today’s span: the number of consecutive days, ending today and going backwards, on which the price was less than or equal to today’s price. Today always counts, so the span is at least 1.

Calls:   next(100) next(80) next(60) next(70) next(60) next(75) next(85)
Returns:     1        1        1        2        1        4        6

On the day of 75, the prices going back are 75, 60, 70, 60 (all ≤ 75) and then 80, which stops it. So the span is 4.

How to think about it

Start with brute force. Keep every price in a list. On each call, walk backwards while prices are <= price. A steadily rising price makes each call walk all the way back, so n calls cost O(n²).

Notice what never matters again. Say today’s price is 75 and yesterday’s was 60. Any future day that reaches back past today must also be >= 75, which means it is also >= 60. So once 60 is covered by 75, 60 is never a stopping point again. You can fold it into today’s count and forget it.

The key insight: keep a stack of (price, span) and let each new price absorb smaller ones. The stack holds only prices that could still stop a future walk. These are in strictly decreasing order from bottom to top. When a new price arrives, pop every pair with price <= today and add its span to today’s span, because that pair’s span already counts the days it absorbed earlier. Then push (price, span).

Which pattern is this? Monotonic stack, “previous greater element”. The span is the distance back to the previous strictly greater price. The tell is “consecutive days going back while the value is at most today’s”, and the word online tells you to process one value at a time.

Approach

1. Keep a stack st of (price, span) pairs.
2. On next(price):
   • Start with span = 1 for today.
   • While the top’s price is <= price, pop it and add its span to span.
   • Push (price, span) and return span.

Solution

class StockSpanner:
    def __init__(self):
        self.st = []                                  # (price, span), prices decreasing
    def next(self, price):
        span = 1
        while self.st and self.st[-1][0] <= price:    # today covers that block of days
            span += self.st.pop()[1]
        self.st.append((price, span)); return span
# sp=StockSpanner(); [sp.next(p) for p in [100,80,60,70,60,75,85]] -> [1,1,1,2,1,4,6]

Dry run

On 75, popping (70, 2) adds two days at once, because 70 had already absorbed the 60 before it.

Complexity

• Time: O(1) amortised per call. Each price is pushed once and popped at most once over the whole sequence, so n calls do O(n) total work. A single call can still pop many pairs.
• Space: O(n). A strictly falling price series keeps every day on the stack.

Edge cases and pitfalls

• Equal prices count. The condition is <=, so next(60) after 60 gives span 2. Using < is a common off-by-one bug here.
• Forgetting to add the popped span (adding 1 instead) undercounts whenever the popped day had already absorbed others.
• First call always returns 1.
• Strictly rising prices return 1, 2, 3, …, and the stack never holds more than one pair.

Related problems

• Daily Temperatures (LeetCode 739): the forward-looking twin: distance to the next warmer day.
• Largest Rectangle in Histogram (LeetCode 84): uses previous-smaller boundaries found the same way.
• Best Time to Buy and Sell Stock (LeetCode 121): another single pass over a price series, tracking a running minimum.