Online Stock Span
Understanding the Problem
Each time next(price) is called, we need to count how many consecutive previous days (including today) had prices less than or equal to the current price. We count backward from today until we reach a day with a strictly higher price, or we run out of days.
The complication is that this is an online problem. We do not get all the prices upfront. Prices arrive one at a time, and we have to answer the span query for each price as it comes in. So we need a data structure that tracks the history and answers these backward-counting queries efficiently.
Once a smaller price is absorbed by a larger one, it never matters again on its own. If price 75 already absorbed the span of 60, 70, and 60 behind it, then when 85 arrives, we do not need to re-check those individual prices. We only need to know that 75 covered a span of 4, and since 85 >= 75, we can jump over all of them in one step. A monotonic stack captures exactly this absorbing behavior.
Key Constraints:
1 <= price <= 10^5→ Prices are positive integers, with no negative values or zeros to handle, and the range stays well withinint, so there are no overflow concerns.- At most
5000calls tonext→ Even an O(n) per call approach (O(n^2) total) gives 25 million operations at the limit, which runs in time. An amortized O(1) approach removes the quadratic blowup and scales past this bound.
Approach 1: Brute Force
Intuition
Store every price we have seen so far in a list. When next(price) is called, walk backward from the most recent price, counting how many consecutive prices are less than or equal to the current price. Stop as soon as we find a price that is strictly greater, or we reach the beginning of the list. This is a direct simulation of the problem statement.
Algorithm
- Maintain a list that stores all prices seen so far.
- When
next(price)is called, append the current price to the list. - Starting from the second-to-last element (the day before today), walk backward.
- Count how many consecutive prices are less than or equal to the current price.
- Return the count plus 1 (to include today itself).
Example Walkthrough
Code
- Time Complexity: O(n) per call, O(n^2) total for n calls. In the worst case (prices in strictly increasing order), each call to
nextwalks all the way back to the beginning of the list. - Space Complexity: O(n). We store every price in the list, so after n calls we use O(n) space.
The bottleneck is the backward scan. When a new price is higher than many previous prices, we re-examine days we already compared against on earlier calls. The next approach reuses the result of those earlier scans, skipping over groups of smaller prices in a single jump.
Approach 2: Monotonic Stack (Optimal)
Intuition
If we already know that the price on day 5 was 75 and it had a span of 4 (meaning days 2 through 5 all had prices <= 75), then when day 6 arrives with a price of 85, we do not need to check days 2, 3, 4, and 5 individually. We check day 5's price (75), see that 85 >= 75, and absorb its entire span of 4. Then we move to whatever day 5 itself could not absorb (day 1) and continue from there.
A monotonic stack lets us jump over these already-summarized spans. We maintain a stack of (price, span) pairs kept in strictly decreasing order of prices from bottom to top. When a new price comes in, we pop every entry whose price is less than or equal to the new price, adding each popped entry's span to the current span. Then we push the new (price, totalSpan) onto the stack.
The stack only keeps prices that act as walls, prices that no later day has surpassed yet. Once a price is surpassed, it gets absorbed and never needs to be checked again.
Absorbing a whole span in one step is safe because of transitivity. The span stored with a wall counts a run of consecutive earlier days that were all <= that wall's price. So if day B's price <= day C's price (C absorbs B), and day A was part of B's span (A's price <= B's price), then A's price <= C's price as well. Every day folded into the wall's span is therefore also <= the new price, so C can absorb the entire span without re-examining the individual days.
This keeps the stack strictly decreasing from bottom to top. Each remaining entry is a price that no later day has surpassed, which is why the next pop comparison is enough to decide whether to keep absorbing.
Algorithm
- Initialize an empty stack that will store (price, span) pairs.
- When
next(price)is called, setspan = 1(counting today). - While the stack is not empty and the top element's price is less than or equal to the current price:
- Pop the top element.
- Add its span to the current span.
- Push
(price, span)onto the stack. - Return span.
Example Walkthrough
Code
- Time Complexity: O(1) amortized per call, O(n) total for n calls. Each price is pushed onto the stack exactly once and popped at most once. The total number of pops across all calls cannot exceed n, so the total work is O(n).
- Space Complexity: O(n). In the worst case (strictly decreasing prices), nothing ever gets popped and the stack grows to size n.