Online Stock Span
Return each day's stock span in amortised O(1) with a monotonic stack of (price, span) pairs that folds smaller prices into today's span.
Problem Understanding
Online Stock Span: design a StockSpanner whose next(price) receives one daily price at a time and returns that day's span, the number of consecutive days up to and including today with a price <= today's.
Example: feeding 100, 80, 60, 70, 60, 75, 85 returns 1, 1, 1, 2, 1, 4, 6. On the day of 75, the prices 60, 70, 60 before it are all smaller, so its span is 4.
The Intuition: Fold Smaller Days Into Today
Counting back day by day is O(n) per call. Instead, keep a monotonic stack of (price, span) pairs, strictly decreasing in price:
- Today's span starts at 1.
- While the top price is
<=today's, pop it and add its span. That span already counts every day it had swallowed, so whole runs of days are added at once. - Push
(price, span)and return the span.
It is the same stack as Next Greater Element I and Daily Temperatures, looking backward instead of forward.
Interactive Walkthrough
Each day's price is on top, with the span returned under it once handled. Below it is the stack of pairs, each price with its span underneath. Watch 75 absorb 60 (span 1) and 70 (span 2) to reach 4.
Dry Run Table
Calls: next with 100, 80, 60, 70, 60, 75, 85
| Price | Popped (span) | Returned | Stack after |
|---|---|---|---|
| 100 | — | 1 | (100,1) |
| 80 | — | 1 | (100,1) (80,1) |
| 60 | — | 1 | … (80,1) (60,1) |
| 70 | 60 (1) | 2 | … (80,1) (70,2) |
| 60 | — | 1 | … (70,2) (60,1) |
| 75 | 60 (1), 70 (2) | 4 | … (80,1) (75,4) |
| 85 | 75 (4), 80 (1) | 6 | (100,1) (85,6) |
The Solution Template
A stack of (price, span) pairs. The C version keeps two parallel arrays sized for LeetCode's 10⁴ calls.
Online Stock Span Code
1var StockSpanner = function() {2 this.stack = [];3};45StockSpanner.prototype.next = function(price) {6 let span = 1;7 while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) span += this.stack.pop()[1];8 this.stack.push([price, span]);9 return span;10};
Edge Cases & Common Mistakes
- Equal prices count: the condition is
<=, not<.5, 5, 5returns1, 2, 3. - Adding 1 per pop: wrong; add the popped pair's stored span, which may cover many days.
- Storing only prices: then you must recount days; store the span (or the day index) with each price.
- Strictly falling prices: nothing is popped and the stack grows to n; every span is 1.
Summary
Keep a decreasing stack of (price, span) pairs. Each next(price) starts at span 1, pops every pair with price <= today and adds its span, then pushes (price, span). Amortised O(1) per call, O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet