Online Stock Span

The key idea

Keep a stack of (price, span) pairs that is monotonically decreasing by price. For each new price, pop every entry whose price is <= price, adding its already-computed span to the current span. This way each day is pushed and popped at most once, so every next call is amortized O(1).

Problem

Design an algorithm that collects daily price quotes for a stock and returns the span of that stock's price for the current day.

The span of the stock's price on the current day is defined as the maximum number of consecutive days (starting from the current day and going backwards) for which the stock price was less than or equal to the price on the current day.

For example, if the prices of the stock in the last 7 days were [100, 80, 60, 70, 60, 75, 85], then the price spans would be [1, 1, 1, 2, 1, 4, 6].

Implement the StockSpanner class:

- StockSpanner() initializes the object of the class.
- int next(int price) returns the span of the stock's price given that today's price is price.

Constraints

1 <= price <= 10^5
At most 10^4 calls will be made to next.

Examples

Input: next(100), next(80), next(60), next(70), next(60), next(75), next(85) Output: 1, 1, 1, 2, 1, 4, 6

Input: next(31), next(41), next(48), next(59), next(79) Output: 1, 2, 3, 4, 5

Complexity

Time: O(1) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →