DSA problem
Online Stock Span
Design an algorithm that collects daily price quotes for a stock and returns the span of the stock's price for the current day. The span of the stock's price on a given day is defined as the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price on that day.
For example, if the prices of a stock for the last seven days are [100, 80, 60, 70, 60, 75, 85], then the spans would be [1, 1, 1, 2, 1, 4, 6]. Notice how the span grows quickly when the current day breaks through a long run of smaller prices.
Implement the StockSpanner class with a single method int next(int price) that records today's price and returns its span. The naive implementation walks back day-by-day from the current day, costing O(n) per call and O(n²) total over n calls — too slow when prices arrive in a stream over many days.
The optimal data structure is a monotonic decreasing stack of (price, span) pairs. When a new price arrives, pop all entries whose price is less than or equal to the new price, accumulating their spans into the new entry's span. Push the merged entry. Each price is pushed once and popped at most once across the entire lifetime of the object, so the amortized cost of next() is O(1).
Examples
StockSpanner; next(100); next(80); next(60); next(70); next(60); next(75); next(85)[1,1,1,2,1,4,6]next(31); next(41); next(48); next(59); next(79)[1,2,3,4,5]next(10); next(9); next(8); next(7)[1,1,1,1]Constraints
- 1 <= price <= 10^5
- At most 10^4 calls will be made to next.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.