Problem Statement
Design a data structure that collects daily stock prices and returns the stock span.
The stock span of today's price is the number of consecutive days (including today) where:
price <= today's price
Brute Force Intuition
In an interview, you can explain it like this:
For every new stock price, traverse backwards day by day until you find a price greater than today's price.
This repeatedly scans previous prices.
Complexity
- Time Complexity: O(N) per query
- Space Complexity: O(N)
Brute Force Code
class StockSpanner {
List<Integer> prices;
public StockSpanner() {
prices = new ArrayList<>();
}
public int next(int price) {
prices.add(price);
int span = 1;
for (int i = prices.size() - 2; i >= 0; i--) {
if (prices.get(i) <= price) {
span++;
} else {
break;
}
}
return span;
}
}
Moving Towards the Optimal Approach
Notice something important.
Suppose today's price is:
100
Previous prices:
60
70
80
These prices are smaller than 100.
Once we process 100:
60
70
80
can never become answers again.
So we remove them immediately.
Pattern Recognition
Whenever you see:
- Previous Greater Element
- Stock Span
- Consecutive Greater/Smaller Elements
Think:
Monotonic Stack
Key Observation
Maintain a stack storing:
(price, span)
Whenever a new price arrives:
Remove every price:
<= Current Price
and add their spans.
Optimal Approach
For every new price:
span = 1
While:
Stack Top <= Current Price
span += previous span
Pop
Finally:
Push:
(Current Price, Span)
Optimal Java Solution
class StockSpanner {
Stack<int[]> st;
public StockSpanner() {
st = new Stack<>();
}
public int next(int price) {
int span = 1;
while (!st.isEmpty() &&
st.peek()[0] <= price) {
span += st.pop()[1];
}
st.push(new int[]{price, span});
return span;
}
}
Dry Run
Prices
100
80
60
70
60
75
85
Price = 100
Stack:
(100,1)
Answer:
1
Price = 80
Stack:
100
80
Answer:
1
Price = 60
Answer:
1
Price = 70
Remove:
60
Span:
1 + 1 = 2
Push:
(70,2)
Answer:
2
Price = 75
Remove:
70
60
Span:
4
Price = 85
Remove:
75
80
Span:
6
Final Output:
[1,1,1,2,1,4,6]
Why Monotonic Stack Works?
Every stock price is:
Pushed Once
Popped Once
Hence:
Overall Complexity
=
O(N)
instead of O(N²).
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(1) Amortized |
| Space Complexity | O(N) |
Interview One-Liner
Maintain a monotonic decreasing stack storing
(price, span)so smaller prices are merged into the current span.
Pattern Learned
Previous Greater Element
+
Consecutive Count
↓
Monotonic Stack
Similar Problems
- Online Stock Span
- Next Greater Element
- Daily Temperatures
- Largest Rectangle in Histogram
- Sum of Subarray Minimums
Memory Trick
Think:
Current Price
↓
Remove Smaller Prices
↓
Add Their Spans
↓
Push (Price, Span)
Mental Model
Need Previous Greater
↓
Monotonic Decreasing Stack
↓
Store Price + Span
Whenever you hear:
"Stock Span"
your brain should immediately think:
Previous Greater Element + Monotonic Stack