Online Stock Span

Online Stock Span

What is this problem about?

The Online Stock Span problem asks you to design a class where next(price) returns how many consecutive days (including today) the stock price has been ≤ today's price. This is the "stock span" — a classic data stream monotonic stack problem. The data stream, monotonic stack, design, and stack interview pattern is the core.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it's the canonical monotonic stack applied to streaming data. Each call to next(price) must return in amortized O(1). The stack maintains (price, span) pairs for unanswered previous days.

Algorithmic pattern used

Monotonic decreasing stack with span accumulation. Maintain a stack of (price, span) pairs. For next(price): initialize span=1. While stack top's price ≤ current price: pop and add its span to current span. Push (price, span). Return span.

Example explanation

Prices: [100,80,60,70,60,75,85].

• next(100): stack=[], span=1. Push (100,1). Return 1.
• next(80): 80<100. Push (80,1). Return 1.
• next(60): 60<80. Push (60,1). Return 1.
• next(70): pop (60,1)→span=2. 70<80. Push (70,2). Return 2.
• next(60): 60<70. Push (60,1). Return 1.
• next(75): pop (60,1)→span=2, pop (70,2)→span=4. 75<80. Push (75,4). Return 4.
• next(85): pop (75,4)→span=5, pop (80,1)→span=6. 85<100. Push (85,6). Return 6.

Common mistakes candidates make

• Recomputing span by scanning backwards (O(n) per call instead of amortized O(1)).
• Not storing span in the stack (losing the accumulated count when popping).
• Using a queue instead of a stack (wrong data structure for this problem).
• Off-by-one: span starts at 1 (counting today itself).

Interview preparation tip

The Online Stock Span problem illustrates why monotonic stacks are O(1) amortized: each element is pushed and popped at most once, so n calls take O(n) total. Storing the accumulated span with each stack entry is the key optimization. Practice this pattern on "streaming range queries" — Online Stock Span is the simplest example, but the same technique extends to sliding window maximum and range minimum queries.