Online Stock Span

The problem

Prices of a stock arrive one day at a time. For each new price, return its 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 counts as one day.

The key insight

When a higher price arrives, the smaller prices before it can never stop a future span: anything that would reach them reaches today first. So fold them into today. Keep a stack of (price, span) pairs with strictly decreasing prices; pop every pair with price at most today's and add its span to today's.

Step-by-step approach

1. Keep a stack of pairs (price, span).
2. For a new price, start with span = 1.
3. While the stack's top price is <= price, pop it and add its span to span.
4. Push (price, span) and return span.

Python solution

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

    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]     # absorb the days that price covered
        self.stack.append((price, span))
        return span

Complexity

Each price is pushed once and popped at most once over all calls, so n calls cost O(n) total. A single call can still pop many entries.

Common mistakes

• Popping entries but forgetting to add their spans, so a span only counts the entries directly popped instead of all the days they covered.
• Using < instead of <=, which stops the span at an equal price even though equal prices count.
• Storing every price and rescanning the history on each call, which is the O(n²) brute force in disguise.

Frequently asked questions

Related problems