Online Stock Span is a streaming-style problem that tests whether you can process data incrementally while keeping past information in a smart, compressed form. You are given daily stock prices one at a time, and for each new price, you must compute its span.
The span of a stock’s price on a given day is defined as the number of consecutive days (including today) for which the price has been less than or equal to today’s price.
For example, if today’s price is higher than yesterday’s and the day before yesterday, the span includes all of those days. If today’s price is lower than yesterday’s, the span is just 1.
The key constraint is that this is an online problem. You cannot see future prices, and you must answer each query as it arrives. That’s what makes it different from classic array-based stock problems.
Why a naive approach breaks down
A straightforward approach is to look backward from today and count how many consecutive previous prices are smaller than or equal to.
That works for a single day, but if prices keep increasing, you end up scanning farther and farther back every time. In the worst case, this leads to quadratic time behavior.
Interviewers use this problem to see whether you can avoid repeated work and recognize patterns that allow you to “skip” unnecessary comparisons.
The key idea behind the solution
The core insight is that not all previous days are equally important.
If you have a previous day with a lower price, and there is a newer day with a higher price, the older day will never matter again on its own. It gets “covered” by the newer, higher price.
This observation leads directly to the idea of using a monotonic stack.
Want to explore more coding problem solutions? Check out the Binary Tree Zigzag Level Order Traversal and Binary Search Tree Iterator.
How the stack-based approach works
You maintain a stack where each entry represents a previous day, but instead of storing just the price, you store:
- the price
- the span associated with that price
The stack is kept in strictly decreasing order of prices from bottom to top.
When a new price arrives, you start with a span of 1 for today.
Then you look at the top of the stack.
If the top price is less than or equal to today’s price, that means today’s span includes all the days represented by that stack entry. So you add its span to today’s span and remove it from the stack.
You keep doing this until either the stack is empty or the top price is greater than today’s price.
Once that process stops, you push today’s price and its computed span onto the stack.
The span you just computed is the answer for today.
Why this works conceptually
Each stack entry represents a block of consecutive days that are all smaller than the price below them in the stack.
By popping and merging spans, you collapse many smaller days into a single entry. This is what prevents repeated scanning of the same days.
Each day’s price is pushed onto the stack once and popped at most once. That guarantees efficiency even for long sequences of increasing prices.
Why this is efficient in practice
Although a single day might cause several pops from the stack, those pops do not repeat across days.
Over the entire sequence of prices, the total number of pushes and pops is linear.
That means the average time per operation is constant, even though individual steps may look more complex.
This “amortized” efficiency is a concept interviewers often want to hear you explain.
Common mistakes candidates make
One frequent mistake is storing only prices and recomputing spans manually, which loses the benefit of compression.
Another is misunderstanding the comparison condition. The problem explicitly says “less than or equal,” and using only “less than” produces incorrect results.
Some candidates also forget that this is an online problem and try to preprocess the entire array, which misses the point of the question.
Top comments (0)