Online Stock Span: Monotonic Stack Pattern
You are designing a class that collects daily stock prices and, for each new price, returns the span: the number of consecutive days (ending with today) where the price was <= today's price. For example, if the last five prices were [100, 80, 60, 70, 60] and today's price is 75, the span is 4 because 75 is greater than or equal to the prices on the previous three days (60, 70, 60) plus today itself.
This is LeetCode 901: Online Stock Span, and it is one of the best problems for learning the monotonic stack pattern. The technique you build here applies to any problem where you need to look backward through a sequence and find the nearest larger element.
Why this problem matters
Many problems require scanning backward through a sequence to find relationships between elements. A brute force approach checks every previous element for each new one, giving O(n^2) total time. The monotonic stack pattern collapses that backward scan into amortized O(1) per element.
Online Stock Span is a clean introduction to this idea because the stack stores both a price and its accumulated span. Each pop absorbs the popped element's span, letting you skip over entire blocks of smaller prices in one step. Once you internalize this pattern, problems like "Daily Temperatures" (LeetCode 739), "Largest Rectangle in Histogram" (LeetCode 84), and "Next Greater Element" (LeetCode 496) all use the same backbone.
The key insight
Instead of scanning backward through every previous price, you maintain a stack where prices are in decreasing order from bottom to top. Each stack entry stores a pair: the price and the span that price covered when it was pushed.
When a new price arrives:
- Start with span = 1 (the current day itself).
- While the stack is not empty and the top price is
<=the new price, pop the top entry and add its span to the current span. - Push the new price with its accumulated span onto the stack.
The popping step is where the magic happens. When you pop an entry, you absorb all the consecutive days that entry already accounted for. You never need to revisit those days again. This is why the stack stays monotonically decreasing: every element that was smaller than a new arrival gets folded into that arrival's span and removed.
The solution
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
span = 1
while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1]
self.stack.append((price, span))
return span
Let's walk through what each piece does.
The __init__ method creates an empty stack. Each entry in the stack will be a tuple of (price, span).
The next method processes one new price. It starts with span = 1 because the current day always counts. Then it enters a while loop: as long as the stack has entries and the top price is <= the new price, it pops that entry and adds its span. This absorbs all the consecutive days that the popped entry already covered. After the loop, the new price and its accumulated span get pushed onto the stack.
The stack always stays in decreasing order. If you see a price of 80 followed by 60, both stay on the stack. But if 75 comes next, the 60 gets popped (absorbed into 75's span). Then 75 sits below 80, and the stack is still decreasing.
The key detail is storing the span alongside each price. Without it, you would need to track indices and compute spans from index differences. By storing the span directly, each pop gives you the exact number of days to absorb, and you never need to know the original indices at all.
Visual walkthrough
Let's trace through the prices [100, 80, 60, 70, 60, 75, 85] step by step. Watch how the stack stays monotonically decreasing and how popping entries accumulates spans.
Step 1: Day 0, price = 100. Stack is empty, so span = 1. Push (100, 1).
No previous prices. The span is just 1 (the day itself). Push onto the stack.
Step 2: Day 1, price = 80. 80 is not >= 100 (top). Span = 1. Push (80, 1).
80 is less than the top of stack (100), so we cannot pop. Span stays 1.
Step 3: Day 2, price = 60. 60 is not >= 80 (top). Span = 1. Push (60, 1).
60 is less than 80. Stack grows to 3 entries, all in decreasing order.
Step 4: Day 3, price = 70. Pop (60, 1) since 70 >= 60. Span = 1 + 1 = 2. Push (70, 2).
70 >= 60, so pop it and absorb its span. Now 70 < 80, so stop. The span of 2 covers days 2 and 3.
Step 5: Day 4, price = 60. 60 is not >= 70 (top). Span = 1. Push (60, 1).
60 is less than 70. No popping. Stack grows to 4 entries.
Step 6: Day 5, price = 75. Pop (60, 1) and (70, 2). Span = 1 + 1 + 2 = 4. Push (75, 4).
75 >= 60, pop and add span 1. Then 75 >= 70, pop and add span 2. Now 75 < 80, stop. Span covers days 2 through 5.
Step 7: Day 6, price = 85. Pop (75, 4) and (80, 1). Span = 1 + 4 + 1 = 6. Push (85, 6).
85 >= 75, pop and add 4. Then 85 >= 80, pop and add 1. Now 85 < 100, stop. Span covers days 1 through 6.
Notice the pattern: when a large price arrives (like 85 on day 6), it pops multiple entries and absorbs all their spans. The stack shrinks dramatically, but no information is lost because the accumulated span captures everything those popped entries represented. This is why the algorithm is O(n) amortized: each element is pushed once and popped at most once across all calls.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Monotonic stack | O(n) amortized | O(n) |
Time is O(n) amortized across n calls to next. Each price is pushed onto the stack exactly once and popped at most once. While a single call to next might pop multiple entries (like day 6 popping two entries), the total number of pops across all calls cannot exceed n. So the average cost per call is O(1).
Space is O(n) in the worst case. If prices arrive in strictly decreasing order (like 100, 90, 80, 70, ...), nothing ever gets popped and the stack grows to hold all n entries.
The building blocks
1. Monotonic stack maintenance
The core pattern of maintaining a stack where elements are in decreasing order:
while stack and stack[-1][0] <= price:
span += stack.pop()[1]
stack.append((price, span))
This is the building block you will reuse in every monotonic stack problem. The condition in the while loop changes depending on the problem (sometimes you want strictly less than, sometimes less than or equal), and what you store in each stack entry varies, but the shape is always the same: pop everything that violates the ordering, then push the new element. You will see this exact pattern in "Daily Temperatures," "Next Greater Element," and "Largest Rectangle in Histogram."
2. Span accumulation through popping
The pattern of absorbing information from popped entries:
span = 1
while stack and stack[-1][0] <= price:
span += stack.pop()[1]
When you pop an entry, you do not just discard it. You absorb the information it carried. In this problem, that information is a span count. In other problems, it might be a count of elements, a sum, or a boundary index. The principle is the same: the popped element's contribution gets folded into the current element, so nothing is lost. This is what makes the monotonic stack an amortized O(1) technique rather than an O(n) per-element scan.
Edge cases
- Strictly increasing prices: every new price pops everything on the stack. The span of the k-th price equals k. The stack never holds more than one entry at a time.
- Strictly decreasing prices: nothing ever gets popped. Every span is 1. The stack grows to hold all n entries.
- All prices the same: since the condition is
<=, every new price pops the previous one. Each span equals its 1-indexed position (1, 2, 3, ...). - Single call: the first call always returns span = 1 regardless of the price, since there are no previous days.
- Very large prices after many small ones: a single call can pop the entire stack, but this is fine because the amortized cost stays O(1) per call.
From understanding to recall
You have seen how the monotonic decreasing stack works: push prices with their spans, pop anything smaller than or equal to the new price, and accumulate the popped spans. The logic is clean and the code is short. But writing it from scratch under interview pressure is a different challenge.
The details that trip people up are subtle. Is the condition < or <=? Do you start span at 0 or 1? Do you store indices or spans? These are not conceptual gaps. They are recall gaps, and they cost people offers.
Spaced repetition is how you close them. You practice writing the monotonic stack maintenance loop and the span accumulation from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "find how far back some condition holds" in a problem description, and the stack template flows out without hesitation.
Related posts
- Daily Temperatures - Another monotonic stack problem where you find the next warmer day for each temperature
- Largest Rectangle in Histogram - Uses a monotonic stack to track boundaries of expanding rectangles
- Evaluate Reverse Polish Notation - A different stack application where you evaluate postfix expressions
CodeBricks breaks Online Stock Span into its monotonic stack maintenance and span accumulation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a stack problem shows up in your interview, you do not think about it. You just write it.