Problem Statement
You are given an array arr[] where arr[i] represents the stock price on the i-th day.
For every day, find the stock span.
The span of a stock's price on a given day is defined as the number of consecutive days ending on that day for which the stock price was less than or equal to the current day's price.
In simpler terms, starting from the current day and moving backward, count how many consecutive days have prices less than or equal to today's price.
Example
Input
[100, 80, 90, 120]
Output
[1, 1, 2, 4]
Understanding the Span
Consider:
Prices
[100, 80, 90, 120]
Day 0
Price:
100
No previous day exists.
Span:
1
Day 1
Price:
80
Previous price:
100 > 80
Span:
1
Day 2
Price:
90
Previous prices:
80 <= 90
100 > 90
Span:
2
Day 3
Price:
120
Previous prices:
90 <= 120
80 <= 120
100 <= 120
Span:
4
Final Answer
[1,1,2,4]
Brute Force Approach
For every day:
Move backward.
Count consecutive days having price less than or equal to the current day's price.
Stop when a larger price is encountered.
Example
for each day i
move left until
arr[j] > arr[i]
Complexity
O(n²)
Because each day may scan all previous days.
For:
n = 100000
this becomes too slow.
Key Observation
Suppose today's price is:
90
We don't care about all previous smaller prices individually.
We only need the nearest previous day having:
price > 90
Why?
Because that day blocks the span.
Everything between that day and today automatically belongs to the span.
Thus the problem becomes:
Find Previous Greater Element
for every index.
This is a classic Monotonic Stack problem.
Monotonic Stack Idea
Maintain a stack containing indices.
The stack stores days in decreasing order of stock prices.
For every new day:
Remove all smaller or equal prices
because they can never act as a boundary for future days.
After popping:
The stack top represents the nearest previous greater price.
Computing Span
Case 1
No greater element exists on the left.
Stack becomes empty
Then the span is:
i + 1
because every previous day belongs to the span.
Case 2
A greater element exists.
Let:
prevGreater = stack.top()
Then:
span = i - prevGreater
Dry Run
Consider:
arr = [10, 4, 5, 90, 120, 80]
Day 0
Price:
10
Stack:
[0]
Span:
1
Day 1
Price:
4
Previous greater:
10
Span:
1
Stack:
[0,1]
Day 2
Price:
5
Remove:
4
Previous greater:
10
Span:
2
Stack:
[0,2]
Day 3
Price:
90
Remove:
5
10
Stack becomes empty.
Span:
4
Day 4
Price:
120
Remove:
90
Stack becomes empty.
Span:
5
Day 5
Price:
80
Previous greater:
120
Span:
1
Final Answer
[1,1,2,4,5,1]
Why Monotonic Stack Works
Whenever a larger price arrives:
Smaller prices lose their importance
because they can never be the nearest greater element for future days.
Thus they are permanently removed.
Each index:
Push → once
Pop → once
Therefore, total operations are linear.
C++ Solution
class Solution {
public:
vector<int> calculateSpan(vector<int>& arr) {
int n = arr.size();
vector<int> span(n);
stack<int> st;
for(int i = 0; i < n; i++) {
while(!st.empty() &&
arr[st.top()] <= arr[i]) {
st.pop();
}
if(st.empty())
span[i] = i + 1;
else
span[i] = i - st.top();
st.push(i);
}
return span;
}
};
Alternative Interpretation
Instead of saying:
Count consecutive smaller prices
you can think:
Find nearest previous greater price
Once that greater price is known:
Span =
Current Index - Previous Greater Index
This viewpoint makes the stack solution very intuitive.
Complexity Analysis
Time Complexity
O(n)
Each index is pushed and popped at most once.
Space Complexity
O(n)
for the stack.
Pattern Recognition
Whenever you see:
Previous Greater Element
Next Greater Element
Stock Span
Daily Temperatures
Histogram Problems
Visibility Problems
Nearest Larger Element
Think:
Monotonic Stack
These problems often reduce from:
O(n²)
to:
O(n)
using the same stack technique.
Key Takeaway
The Stock Span Problem is fundamentally a Previous Greater Element problem.
For every day, we find the nearest previous day having a strictly greater stock price. The distance between the current day and that boundary gives the span.
Using a monotonic decreasing stack allows us to process all days in linear time, making it one of the most important applications of the Monotonic Stack pattern.
Summary
The Stock Span Problem can be efficiently solved using a monotonic decreasing stack. Instead of checking all previous days, we find the nearest previous day with a greater stock price. This transforms a quadratic-time solution into a linear-time solution, making it suitable for large datasets and serving as a classic example of the Monotonic Stack pattern.