Stock Span Problem: LeetCode 901 Solution Explained

Online Stock Span (LeetCode #901) is one of the best problems to learn how the monotonic stack pattern applies outside of textbook examples. Instead of processing a full array at once, you handle one price at a time — making it a streaming or "online" algorithm.

The stock span problem on LeetCode asks you to design a class that receives daily stock prices and returns the span for each day. The span counts how many consecutive days (including today) the price was less than or equal to today's price. It is a Medium-difficulty problem and a favorite in coding interviews at companies like Amazon and Google.

If you have already solved Daily Temperatures or Next Greater Element, you will recognize the monotonic stack pattern here. The twist is that you must maintain state across multiple function calls rather than iterating through a fixed array.

The StockSpanner class has a single method: next(price). Each time you call next, you pass in today's stock price and receive the span — the number of consecutive days going back (including today) where the price was less than or equal to the current price.

For example, given prices [100, 80, 60, 70, 60, 75, 85], the spans would be [1, 1, 1, 2, 1, 4, 6]. On the day with price 75, you look back and see 60, 70, 60 are all less than or equal to 75, so the span is 4 (including the current day).

The key insight is that the span can reach arbitrarily far back. If prices have been non-decreasing from day one, then today's span equals the total number of days seen so far. A naive approach that scans backward each time will be too slow.

The simplest approach stores all previous prices in an array. For each call to next(price), you walk backward through the array counting consecutive days where the price was less than or equal to the current price. You stop as soon as you find a higher price.

This gives you O(n) time per call in the worst case, where n is the number of days processed so far. Over n total calls, the worst-case total time is O(n squared). For a strictly non-decreasing sequence, every call scans all the way back to the beginning.

The brute force is correct and easy to implement, but it does not pass the LeetCode time limit for large inputs. You need a way to skip over days you have already accounted for — and that is exactly what a monotonic stack provides.

The optimal solution uses a monotonic decreasing stack. Instead of storing every single price, the stack holds (price, span) pairs. The stack maintains a strict decreasing order of prices from bottom to top.

When you call next(price), you initialize a span counter at 1 (for the current day). Then you check the top of the stack: if the top price is less than or equal to the current price, you pop it and add its span to your counter. You keep popping until the stack is empty or the top price is strictly greater than the current price.

After popping, you push (price, accumulated_span) onto the stack. The accumulated span captures all the days that were already counted by the popped elements, so you never need to revisit them.

This works because when you pop an element from the stack, its span has already been folded into the current element's span. No information is lost. The stack essentially compresses the history — it remembers only the prices that could still be relevant as a "barrier" for future days.

At first glance, popping multiple elements per call looks like it could be expensive. But the amortized analysis tells a different story. Each element is pushed onto the stack exactly once and popped at most once across all calls to next.

If you make n calls total, there are at most n pushes and at most n pops — giving you 2n operations total. Spread across n calls, that is O(1) amortized time per call. The worst-case single call might pop many elements, but those elements will never be popped again.

This is the same amortized argument used in other monotonic stack problems like Daily Temperatures and Next Greater Element. The key is that work done in expensive calls "pays for" the cheap calls that follow. Space complexity is O(n) in the worst case for the stack, which occurs when prices are strictly decreasing.

Strictly increasing prices represent the most expensive single-call scenario. Each new price pops everything on the stack, so day k has span k. But as discussed, the amortized cost remains O(1) per call because each element is only pushed and popped once.

Strictly decreasing prices are the opposite extreme. Nothing ever gets popped — every span is 1 and the stack grows to hold all n elements. This is the worst case for space usage.

When all prices are the same, each call pops the top element (same price counts as <= current), accumulates its span, and pushes a new entry. The stack never grows beyond size 1 after the first call, and spans grow as 1, 2, 3, 4, and so on.

These edge cases are worth walking through during an interview to demonstrate that you understand how the stack behaves under different input distributions.

LeetCode 901 is valuable because it tests the monotonic stack in a streaming context. Unlike Daily Temperatures where you have the entire array upfront, here you process one element at a time and must return an answer immediately. This forces you to truly understand the data structure rather than relying on array-level tricks.

The accumulation technique — storing (price, span) pairs and folding popped spans into the current entry — is a pattern you will see again in problems like Largest Rectangle in Histogram and Sum of Subarray Minimums. Mastering it here gives you a template for harder problems.

If you want to build lasting intuition for monotonic stack problems, review this problem alongside Daily Temperatures and Next Greater Element. YeetCode flashcards help you drill these patterns with spaced repetition so the approach becomes automatic during interviews.