Online Stock Span
Last Updated: April 1, 2026
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 are counting backward from today until we hit a day with a strictly higher price, or we run out of days.
The tricky part is that this is an online problem. We do not get all the prices upfront. Prices arrive one at a time, and we need to answer the span query for each price as it comes in. So we need a data structure that efficiently tracks the history and answers these "how far back can I go?" queries.
The key observation is that 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 comes along, we do not need to re-check those individual prices. We just need to know that 75 covered a span of 4, and since 85 >= 75, we can jump over all of them. This "absorbing" behavior is exactly what a monotonic stack enables.
Key Constraints:
1 <= price <= 10^5→ Prices are positive integers. No negative prices or zeros to handle. The range is moderate, so no overflow concerns.- At most
5000calls tonext→ With up to 5000 operations, even an O(n) per call approach (O(n^2) total) would give 25 million operations, which is acceptable. But an amortized O(1) approach is cleaner and scales better.
Approach 1: Brute Force
Intuition
The simplest approach is to 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 the most straightforward translation of the problem statement into code. No clever tricks, just direct simulation.
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 earlier. What if we could remember the result of those earlier scans and skip over groups of smaller prices in one jump?
Approach 2: Monotonic Stack (Optimal)
Intuition
Here is the key insight: if we already know that the price on day 5 was 75 and it had a span of 4 (meaning days 2-5 all had prices <= 75), then when day 6 comes with a price of 85, we do not need to check days 2, 3, 4, and 5 individually. We just 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.
This "jump over already-summarized spans" behavior is what a monotonic stack gives us. We maintain a stack of (price, span) pairs, where the stack is always 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 are "walls" -- prices that some future day has not yet been able to surpass. Once a price is surpassed, it gets absorbed and never needs to be checked again.
The monotonic stack maintains an invariant: from bottom to top, prices are strictly decreasing. Every element on the stack represents a "wall" that no subsequent price has managed to surpass yet. When a new price surpasses a wall, that wall's entire span gets absorbed because every day the wall covered was also smaller than the new price.
This works because of a transitive property: if day A's price was <= day B's price, and day B's price <= day C's price, then day A's price <= day C's price. So when C absorbs B's span, it implicitly absorbs all the days B had already absorbed.
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.