Community Problem
Online Stock Span
Difficulty: Medium
Design an online structure that returns the streak of consecutive previous days with price <= today, using a monotonic stack of (price, span) pairs.
Online Stock Span
Design an online structure that returns the streak of consecutive previous days with price <= today, using a monotonic stack of (price, span) pairs.
By @nehawood
March 20, 2026
·
Updated May 20, 2026
349 views
7
Rate
Got asked this on a Bloomberg phone screen and the trap was the streaming nature: the interviewer pushes O(n) days at you and watches whether your per-call cost stays amortized O(1) instead of degrading to O(n). The monotonic stack of (price, span) pairs is the answer; the trick is what you store on the stack and what you do during the pop loop.
Online Stock Span
Design a class StockSpanner that processes the daily prices of a stock as a stream and returns the span of the most recent day's price. The span is defined as the maximum number of consecutive days (ending with today, going backwards) where the price has been less than or equal to today's price.
For example, with daily prices [100, 80, 60, 70, 60, 75, 85], the span values are [1, 1, 1, 2, 1, 4, 6].
Implement:
StockSpanner()constructs the spanner.int next(int price)returns the span for today's priceprice.
The next method is called once per day in chronological order.
Examples
Example 1:
- Input: feed
[100, 80, 60, 70, 60, 75, 85]one at a time. - Output:
[1, 1, 1, 2, 1, 4, 6] - Explanation: At day 3 (price 70), days 60 and 70 are <= 70 so span is 2. At day 5 (price 75), 75 >= 60, 70, 60, 75 so span is 4. At day 6 (price 85), the chain reaches all the way back except for the leading 100, so span is 6.
Example 2:
- Input: feed
[10, 4, 5, 90, 120, 80] - Output:
[1, 1, 2, 4, 5, 1] - Explanation: 90 swallows 4, 5, and itself for span 4. 120 swallows everything before it for span 5.
Example 3:
- Input: feed
[31, 41, 48, 59, 79] - Output:
[1, 2, 3, 4, 5] - Explanation: Strictly increasing sequence; each new price absorbs the entire history.
Example 4:
- Input: feed
[7, 6, 5, 4, 3] - Output:
[1, 1, 1, 1, 1] - Explanation: Strictly decreasing sequence; every span is 1.
Constraints
1 <= price <= 10^5- At most
10^4calls tonext.
Follow-up
What is the amortized time complexity of next? Why does a naive backward-scan give O(n^2) for n calls but the monotonic stack gives O(n) total?
Solution
Hints
Approach
The naive solution scans backwards from the current day until it finds a strictly larger previous price. That is O(n) per call and O(n^2) total. The monotonic-stack version stores summarized previous days as (price, span) pairs and runs in O(n) total time across all calls.
Key insight
If yesterday's price was p_y with span s_y, and today's price p_t is >= p_y, then yesterday's s_y days are all swallowed into today's span (because they were all <= p_y <= p_t). So instead of remembering each individual day, remember each "summary block": a price and the span it absorbed. New days that beat the top of the stack absorb that block in one step (constant work per pop). The stack stays strictly decreasing in price.
Algorithm
- Maintain a stack of
(price, span)pairs. - On
next(price):- Set
span = 1(today itself). - While the stack is non-empty AND
stack.top.price <= price: pop the top pair and add its span tospan. - Push
(price, span)and returnspan.
Complexity
Metric Value
-------------- -------------
next (worst) O(n)
next (amortized) O(1)
Overall (n calls) O(n)
Space O(n) for the stack in the worst case (strictly decreasing input)Every (price, span) pair is pushed exactly once and popped at most once over the lifetime of the spanner.
Why it works
The stack is always a strictly decreasing sequence of prices from bottom to top. An incoming price either fits on top (when it is < current top, span = 1) or it absorbs a contiguous suffix of the stack (when it is >= some elements). Because each absorbed block already has its span computed correctly, the new span is the sum of those absorbed spans plus 1 for today. Strict decrease guarantees the popped suffix is exactly the contiguous run of <= price days from today backwards.
Pitfalls
- Using
<instead of<=: the span definition is<= today, so pop whiletop.price <= price. - Iterating the stack with
for...ofin Sandpack JS: arrays are safe, but if you use aMapof indices instead, ES5 transpilation will silently break. Stick to arrays here. - Storing days individually instead of summarizing: same correctness but
O(n^2)overncalls because re-scanning popped days does not happen in the monotonic version.
Solution Code