Online Stock Span — Class Design with Stack

Design a class that collects daily stock prices and returns the span of each day’s price. The span is the number of consecutive days (ending today) where the price was less than or equal to today’s price.

The Challenge

Unlike the batch version where you have all prices upfront, here prices arrive one at a time via next(price). You can’t look ahead.

Solution — Price-Span Pairs

Store (price, span) pairs on the stack. When a new price arrives, pop all smaller-or-equal prices and absorb their spans.

class StockSpanner:
    def __init__(self):
        self.stack = []  # (price, span) pairs
    
    def next(self, price):
        """
        Return the span for this price.
        Time: O(1) amortized, Space: O(n)
        """
        span = 1

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

        self.stack.append((price, span))
        return span

Trace

Call        | price | stack (price,span)      | span
------------|-------|-------------------------|-----
next(100)   | 100   | [(100,1)]               | 1
next(80)    | 80    | [(100,1),(80,1)]         | 1
next(60)    | 60    | [(100,1),(80,1),(60,1)]  | 1
next(70)    | 70    | pop(60,1) → span=2       | 2
            |       | [(100,1),(80,1),(70,2)]  |
next(60)    | 60    | [(100,1),(80,1),(70,2),(60,1)] | 1
next(75)    | 75    | pop(60,1),(70,2) → span=4| 4
            |       | [(100,1),(80,1),(75,4)]  |
next(85)    | 85    | pop(75,4),(80,1) → span=6| 6
            |       | [(100,1),(85,6)]         |

Why Price-Span Pairs?

When we pop a price, we lose information about the days it represented. By storing the accumulated span with each price, popping absorbs all the days that price covered. This is why we add stack.pop()[1] to the current span.

Amortized Analysis

Each price is pushed exactly once and popped at most once across all calls to next(). Over n calls:

• Total pushes = n
• Total pops ≤ n
• Total work = O(2n) = O(n)
• Amortized per call = O(1)

Worst case for a single call is O(n) (price higher than all previous), but this can’t happen every call.

Edge Cases

• First call — always returns 1
• Monotonically increasing — each call pops everything, span grows
• Monotonically decreasing — each call returns 1, stack grows
• All same prices — each new price absorbs all previous, span = call number

When to Use This Pattern

The price-span pair technique works for any online/streaming problem where:

• You need to aggregate information from elements you’re about to discard
• The aggregation is associative (sums, counts, max/min)

Related Problems

• Stock Span (batch) — index-based approach
• Next Greater Element (LeetCode 496/503)
• Daily Temperatures (LeetCode 739)
• Design patterns with amortized O(1) — similar to queue-from-two-stacks