126. Online Stock Span
🔗 LeetCode Problem: 901. Online Stock Span
📊 Difficulty: Medium
🏷️ Topics: Stack, Design, Monotonic Stack, Data Stream
Problem Statement
Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day.
The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.
Implement the StockSpanner class:
- StockSpanner() Initializes the object of the class.
- int next(int price) Returns the span of the stock's price given that today's price is price.
Example 1:
Input:
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output:
[null, 1, 1, 1, 2, 1, 4, 6]
Explanation:
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2 (70 >= 60, count 2 days)
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4 (75 >= 60, 70, 60, 75, count 4 days)
stockSpanner.next(85); // return 6 (85 >= all previous, count 6 days)
Constraints:
- 1 <= price <= 10^5
- At most 10^4 calls will be made to next.
🌟 Understanding the Problem
What is "Span"?
The span is: "How many consecutive days going BACKWARD had price <= today's price?"
Example: Prices so far: [100, 80, 60, 70]
↑ ↑ ↑ ↑
day0 day1 day2 day3
For day 3 (price 70):
Look backward: day 2 (60) ≤ 70? YES, count it
day 1 (80) ≤ 70? NO, STOP!
Span = 2 (day 3 itself + day 2)
Visual representation:
Day: 0 1 2 3 4 5 6
Price: 100 80 60 70 60 75 85
Span: 1 1 1 2 1 4 6
Day 3 (70): Look back → 60 ✓, stop at 80
Span = 2 (days 2-3)
Day 5 (75): Look back → 60 ✓, 70 ✓, 60 ✓, stop at 80
Span = 4 (days 2-5)
Day 6 (85): Look back → all prices ≤ 85
Span = 6 (days 1-6, but not day 0!)
Key observation: We're counting backward until we hit a HIGHER price (or beginning)!
💡 Connection to Previous Problems
How Does This Relate to What We've Learned?
┌─────────────────────────────────────────────────────────┐
│ Daily Temperatures │ Online Stock Span │
├─────────────────────────────────────────────────────────┤
│ Find: Next GREATER │ Find: Previous GREATER │
│ going FORWARD │ going BACKWARD │
│ │ │
│ Question: │ Question: │
│ "How far to next warmer?" │ "How far back until │
│ │ higher price?" │
│ │ │
│ Direction: → │ Direction: ← │
│ │ │
│ Return: Distance forward │ Return: Distance backward│
└─────────────────────────────────────────────────────────┘
The twist:
Daily Temperatures: Array given upfront
Stock Span: Prices arrive ONE AT A TIME (streaming!)
This is an ONLINE algorithm - we can't see future prices!
💡 How to DISCOVER the Solution
Let me show you the natural thought progression.
🎯 STEP 1: Understanding the Streaming Nature
What makes this problem different?
Normal array problem:
prices = [100, 80, 60, 70, 60, 75, 85]
Process all at once
Streaming problem (this one):
Day 0: next(100) → process
Day 1: next(80) → process
Day 2: next(60) → process
...
We process ONE price at a time!
We can't look ahead, only backward!
What does this mean?
1. We need to REMEMBER previous prices
2. We can't use future prices (we don't have them yet!)
3. Must be efficient - could have 10,000 calls
🎯 STEP 2: First Attempt - Store Everything
Naive thinking:
"I'll store all previous prices in a list!
Then for each new price, scan backward until I find a higher one."
class StockSpanner {
List<Integer> prices;
StockSpanner() {
prices = new ArrayList<>();
}
int next(int price) {
prices.add(price);
int span = 1; // Count today
// Scan backward
for (int i = prices.size() - 2; i >= 0; i--) {
if (prices.get(i) <= price) {
span++;
} else {
break; // Found higher price, stop
}
}
return span;
}
}
Does it work?
Yes! ✓
Example: [100, 80, 60, 70]
next(100): prices=[100], span=1 ✓
next(80): prices=[100,80], scan back: 100>80, stop, span=1 ✓
next(60): prices=[100,80,60], scan: 80>60, stop, span=1 ✓
next(70): prices=[100,80,60,70], scan: 60≤70 (count), 80>70 (stop), span=2 ✓
Is it fast?
NO! ❌
Time per call: O(n) where n = number of previous prices
Space: O(n) to store all prices
Worst case: Strictly increasing prices [1,2,3,4,...,10000]
Each call scans ALL previous prices!
Call 10000 scans 9999 prices → very slow!
🎯 STEP 3: What Are We Repeating?
Let's trace carefully:
Prices: [100, 80, 60, 70, 60, 75]
Day 5 (price 75):
Scan back: 60 ≤ 75 ✓ (count)
70 ≤ 75 ✓ (count)
60 ≤ 75 ✓ (count)
80 > 75 ✗ (stop)
Span = 4
But wait! We already knew from Day 3 (price 70):
70's span was 2 (covered days 2-3)
So when we're at day 5:
75 ≤ all prices that 70 covered!
We don't need to check them individually!
The insight:
If current price >= previous price:
Current price also covers everything previous price covered!
This is like "telescoping" - we can jump over ranges!
🎯 STEP 4: Can We Skip Already-Counted Ranges?
New idea:
What if we store SPANS along with prices?
When we see a new price:
- If new price >= previous price
- We can add previous span to our count
- Skip those days entirely!
Let's trace this:
Prices: [100, 80, 60, 70]
Spans: [ 1, 1, 1, ?]
Day 3 (price 70):
Compare with day 2 (60): 70 >= 60? YES
Add span of day 2 (which is 1)
Current span = 1 + 1 = 2
Compare with day 1 (80): 70 >= 80? NO
Stop!
Span = 2 ✓
But there's a problem:
After adding day 2's span, we need to check day 1.
But day 1 is NOT immediately before day 2!
We need to "jump back" by the span amount.
This requires knowing which day to check next...
🎯 STEP 5: What Information Do We Actually Need?
Think about what we're doing:
For each new price, we're asking:
"Going backward, which is the FIRST day with price > current?"
Everything between that day and today is part of our span!
This sounds familiar!
Daily Temperatures: "Going forward, find next GREATER"
Stock Span: "Going backward, find previous GREATER"
Same pattern, opposite direction!
From Daily Temperatures, we learned:
Use a STACK to track "waiting" elements!
But here it's reversed - we're looking BACKWARD not FORWARD.
How does that change things?
🎯 STEP 6: Adapting the Stack Pattern
In Daily Temperatures:
Stack stores days WAITING for warmer weather
When warmer day arrives, pop and resolve
In Stock Span:
Stack stores days that might be "boundaries" (higher prices)
When new price arrives, pop all smaller/equal prices
What remains is the previous HIGHER price
Let's think about what to store:
Option 1: Store prices only
Stack: [100, 80]
New price: 70
Check: 80 > 70? YES, this is the boundary!
But wait... span is how many DAYS.
We need to know the DAY index, not just the price!
PROBLEM: Can't calculate span without knowing positions! ❌
Option 2: Store (price, day_index) pairs
Stack: [(100, 0), (80, 1)]
New price: 70 at day 3
Check: 80 > 70? YES, this is the boundary!
Boundary is at day 1
Span = 3 - 1 = 2 ✓
This works! But do we need day index?
Wait, let's reconsider:
Actually, we don't count DAYS in the calendar.
We count consecutive days in our STREAM.
If we maintain a counter, we can just use: current_count - boundary_count
Option 3: Store (price, count) pairs
Stack: [(100, 1), (80, 2)] ← (price, how many prices we've seen)
New price: 70 (count = 3)
Check: 80 > 70? YES!
Span = current_count - count_before_boundary
= 3 - 2 = 1?
Wait, that's wrong! Should be 2...
Option 4: Store (price, span) pairs
Let me think differently...
When we pop elements, we're saying:
"These popped elements are <= current price"
"Current price covers them all"
If we store how many days each element already covered (its span):
We can add up all those spans!
🎯 STEP 7: The Breakthrough - Store (price, span)
The key insight:
Each element in stack has:
- A price
- How many consecutive days going back IT covered (its span)
When we pop an element:
- Current price >= that price
- Current price ALSO covers everything that price covered
- Add that span to our current span!
Let's trace this:
Prices arrive: [100, 80, 60, 70]
Day 0: price=100
Stack: []
span = 1 (just itself)
Push (100, 1)
Stack: [(100, 1)]
Day 1: price=80
Stack: [(100, 1)]
Check: 100 > 80? YES, don't pop (it's a boundary)
span = 1 (just itself)
Push (80, 1)
Stack: [(100, 1), (80, 1)]
Day 2: price=60
Stack: [(100, 1), (80, 1)]
Check: 80 > 60? YES, don't pop
span = 1
Push (60, 1)
Stack: [(100, 1), (80, 1), (60, 1)]
Day 3: price=70
Stack: [(100, 1), (80, 1), (60, 1)]
Check: 60 <= 70? YES, pop!
span = 1 (current) + 1 (popped span) = 2
Stack: [(100, 1), (80, 1)]
Check: 80 <= 70? NO, stop popping
span = 2 ✓
Push (70, 2)
Stack: [(100, 1), (80, 1), (70, 2)]
This works! Let's verify with more:
Continue: next(60)
Day 4: price=60
Stack: [(100, 1), (80, 1), (70, 2)]
Check: 70 <= 60? NO, stop
span = 1
Push (60, 1)
Stack: [(100, 1), (80, 1), (70, 2), (60, 1)]
Continue: next(75)
Day 5: price=75
Stack: [(100, 1), (80, 1), (70, 2), (60, 1)]
Check: 60 <= 75? YES, pop!
span = 1 + 1 = 2
Stack: [(100, 1), (80, 1), (70, 2)]
Check: 70 <= 75? YES, pop!
span = 2 + 2 = 4
Stack: [(100, 1), (80, 1)]
Check: 80 <= 75? NO, stop
span = 4 ✓
Push (75, 4)
Stack: [(100, 1), (80, 1), (75, 4)]
Beautiful! It works!
🎯 STEP 8: Why Does This Work?
The magic of storing spans:
When we pop (price, span):
- That element covered `span` consecutive days
- Current price >= that price
- So current price ALSO covers those `span` days
- We inherit that span!
Example:
(70, 2) means: "70 covered 2 consecutive days: day 2 and day 3"
When 75 pops (70, 2):
75 >= 70, so 75 also covers days 2 and 3
We add 2 to our span!
Why we can skip those days:
We don't need to check days 2 and 3 individually!
We know 70 >= all of them (because 70's span was 2)
And we know 75 >= 70
Therefore: 75 >= all of them (transitivity!)
This is the "telescoping" optimization!
🎯 STEP 9: Why Stack Maintains Decreasing Prices
Observation:
Stack prices are always STRICTLY DECREASING (top to bottom)
Why?
When we see price P:
- We pop ALL prices <= P
- Remaining prices are > P
- We push P
- Stack is still decreasing!
Example:
Stack: [100, 80, 60] (decreasing)
New: 70
Pop 60 (60 <= 70)
Stack: [100, 80]
Can't pop 80 (80 > 70)
Push 70
Stack: [100, 80, 70] (still decreasing!)
Why this property is powerful:
1. Top of stack = most recent lower/equal price
2. When we can't pop anymore, we found the boundary
3. Stack represents "potential boundaries" in decreasing order
🎯 STEP 10: The Complete Picture
What we've discovered:
1. Store (price, span) pairs in stack
2. Stack maintains strictly decreasing prices
3. When new price arrives:
- Pop all elements with price <= current
- Add their spans to current span
- Push (current price, current span)
4. Span accumulates as we pop (telescoping!)
5. Each price pushed/popped at most once → O(1) amortized
The algorithm:
class StockSpanner {
Stack<(price, span)> stack
next(price):
span = 1 // Count today
while stack not empty AND stack.top.price <= price:
popped = stack.pop()
span += popped.span // Inherit covered days!
stack.push((price, span))
return span
}
Why it's optimal:
Time: O(1) amortized per call
- Each price pushed once
- Each price popped once (total)
- Amortized: constant per operation
Space: O(n) worst case
- Strictly decreasing sequence: all prices in stack
- Example: [100, 99, 98, ..., 1]
🎯 Approach 1: Brute Force (Store All Prices)
Implementation
class StockSpanner {
private List<Integer> prices;
public StockSpanner() {
prices = new ArrayList<>();
}
public int next(int price) {
prices.add(price);
int span = 1; // Count current day
// Scan backward from second-to-last
for (int i = prices.size() - 2; i >= 0; i--) {
if (prices.get(i) <= price) {
span++;
} else {
break; // Found higher price, stop
}
}
return span;
}
}
Complexity Analysis
⏰ Time: O(n) per call in worst case
For each next() call:
- Add to list: O(1)
- Scan backward: O(n) where n = number of previous prices
Worst case: Strictly increasing [1, 2, 3, 4, ..., 10000]
Call 1: scan 0 elements
Call 2: scan 1 element
Call 3: scan 2 elements
...
Call n: scan n-1 elements
Total: 0 + 1 + 2 + ... + (n-1) = O(n²) for all calls!
💾 Space: O(n)
Store all n prices in ArrayList
🎯 Approach 2: Monotonic Stack (Optimal)
The Strategy
1. Use stack to store (price, span) pairs
2. Stack maintains STRICTLY DECREASING prices
3. When new price arrives:
- Pop all smaller/equal prices
- Accumulate their spans
- Push new (price, span)
4. Telescoping optimization: skip entire ranges!
Why Stack? (Complete Reasoning)
Why not store in an array?
Array: Need to know which indices to check
- After accumulating a span, which index next?
- Complex index arithmetic
- Would need auxiliary data structures
Stack: Natural LIFO for "going backward"
- Most recent is top
- Pop reveals previous boundary
- Clean and simple!
Why not a queue?
Queue: FIFO (First In, First Out)
- Oldest element at front
- But we check MOST RECENT first!
- Wrong order!
Stack: LIFO (Last In, First Out)
- Most recent element at top
- Matches our "look backward" pattern
- Correct order! ✓
Why store (price, span) not just price?
Just price:
Stack: [100, 80, 60]
New: 70
Pop 60... then what?
How many days did 60 represent? DON'T KNOW! ❌
With (price, span):
Stack: [(100,1), (80,1), (60,1)]
New: 70
Pop (60,1) → span = 1 + 1 = 2 ✓
We inherit the days! ✓
Implementation
class StockSpanner {
// Stack stores (price, span) pairs
// We'll use two parallel stacks for simplicity in Java
private Stack<Integer> prices;
private Stack<Integer> spans;
public StockSpanner() {
prices = new Stack<>();
spans = new Stack<>();
}
public int next(int price) {
int span = 1; // Count today
// Pop all prices <= current price
while (!prices.isEmpty() && prices.peek() <= price) {
prices.pop();
span += spans.pop(); // Inherit covered days!
}
// Push current price and its span
prices.push(price);
spans.push(span);
return span;
}
}
Alternative Implementation (Using Pair Class)
class StockSpanner {
// Custom pair class
private static class PriceSpan {
int price;
int span;
PriceSpan(int price, int span) {
this.price = price;
this.span = span;
}
}
private Stack<PriceSpan> stack;
public StockSpanner() {
stack = new Stack<>();
}
public int next(int price) {
int span = 1;
// Pop all elements with price <= current
while (!stack.isEmpty() && stack.peek().price <= price) {
span += stack.pop().span;
}
// Push current (price, span)
stack.push(new PriceSpan(price, span));
return span;
}
}
Line-by-Line Explanation
private Stack<Integer> prices;
private Stack<Integer> spans;
// WHY two stacks? To store (price, span) pairs
// Could use Pair class, but two stacks is simpler in Java
// Both stacks stay synchronized
public StockSpanner() {
prices = new Stack<>();
spans = new Stack<>();
}
// Initialize empty stacks
// WHY? No previous prices yet
public int next(int price) {
int span = 1;
// WHY start at 1? Today itself counts!
while (!prices.isEmpty() && prices.peek() <= price) {
// WHY while? Could be multiple days to pop
// WHY peek()? Check top without removing yet
// WHY <= ? Equal prices also get covered!
prices.pop();
span += spans.pop();
// WHY pop both? Keep stacks synchronized
// WHY add span? Inherit covered days!
// This is the telescoping optimization!
}
prices.push(price);
spans.push(span);
// WHY push both? Store current (price, span) pair
// This becomes a potential boundary for future prices
return span;
// Return the calculated span for today
}
Detailed Dry Run
Calls: next(100), next(80), next(60), next(70), next(60), next(75), next(85)
═══════════════════════════════════════════════════════════
Call 1: next(100)
═══════════════════════════════════════════════════════════
price = 100
span = 1
While: prices.isEmpty()? YES, skip
WHY? No previous prices to compare
Push: prices=[100], spans=[1]
Return: 1 ✓
Stack state:
prices: [100]
spans: [1]
═══════════════════════════════════════════════════════════
Call 2: next(80)
═══════════════════════════════════════════════════════════
price = 80
span = 1
While: !prices.isEmpty() && prices.peek() <= 80?
TRUE && 100 <= 80? FALSE
WHY FALSE? 100 > 80, it's a boundary, don't pop
Push: prices=[100, 80], spans=[1, 1]
Return: 1 ✓
Stack state:
prices: [100, 80] ← decreasing!
spans: [1, 1]
═══════════════════════════════════════════════════════════
Call 3: next(60)
═══════════════════════════════════════════════════════════
price = 60
span = 1
While: !prices.isEmpty() && prices.peek() <= 60?
TRUE && 80 <= 60? FALSE
WHY? 80 > 60, boundary
Push: prices=[100, 80, 60], spans=[1, 1, 1]
Return: 1 ✓
Stack state:
prices: [100, 80, 60] ← still decreasing!
spans: [1, 1, 1]
═══════════════════════════════════════════════════════════
Call 4: next(70)
═══════════════════════════════════════════════════════════
price = 70
span = 1
While: !prices.isEmpty() && prices.peek() <= 70?
TRUE && 60 <= 70? TRUE ← ENTER LOOP
Iteration 1:
Pop price: 60
Pop span: 1
span = 1 + 1 = 2
WHY add? 70 covers day 3 (60's day) + itself!
Stack: prices=[100, 80], spans=[1, 1]
Loop check: !prices.isEmpty() && 80 <= 70?
TRUE && FALSE? FALSE ← EXIT
WHY exit? 80 > 70, found boundary!
Push: prices=[100, 80, 70], spans=[1, 1, 2]
Return: 2 ✓
Stack state:
prices: [100, 80, 70]
spans: [1, 1, 2]
Meaning: 70 covered 2 consecutive days (days 2-3)
═══════════════════════════════════════════════════════════
Call 5: next(60)
═══════════════════════════════════════════════════════════
price = 60
span = 1
While: !prices.isEmpty() && prices.peek() <= 60?
TRUE && 70 <= 60? FALSE
WHY? 70 > 60, boundary
Push: prices=[100, 80, 70, 60], spans=[1, 1, 2, 1]
Return: 1 ✓
Stack state:
prices: [100, 80, 70, 60]
spans: [1, 1, 2, 1]
═══════════════════════════════════════════════════════════
Call 6: next(75)
═══════════════════════════════════════════════════════════
price = 75
span = 1
While: !prices.isEmpty() && prices.peek() <= 75?
TRUE && 60 <= 75? TRUE ← ENTER
Iteration 1:
Pop price: 60
Pop span: 1
span = 1 + 1 = 2
Stack: prices=[100, 80, 70], spans=[1, 1, 2]
Loop check: 70 <= 75? TRUE ← CONTINUE
Iteration 2:
Pop price: 70
Pop span: 2 ← This is KEY!
span = 2 + 2 = 4
WHY? 70 covered 2 days (days 2-3)
75 >= 70, so 75 covers those 2 days too!
Plus day 4 (60's day) and itself (day 5)
Total: 4 days!
Stack: prices=[100, 80], spans=[1, 1]
Loop check: 80 <= 75? FALSE ← EXIT
WHY? 80 > 75, boundary found!
Push: prices=[100, 80, 75], spans=[1, 1, 4]
Return: 4 ✓
Stack state:
prices: [100, 80, 75]
spans: [1, 1, 4]
Verification: 75 covered days 2, 3, 4, 5 (4 days) ✓
Day 2: 60 <= 75 ✓
Day 3: 70 <= 75 ✓
Day 4: 60 <= 75 ✓
Day 5: 75 itself ✓
═══════════════════════════════════════════════════════════
Call 7: next(85)
═══════════════════════════════════════════════════════════
price = 85
span = 1
While: !prices.isEmpty() && prices.peek() <= 85?
TRUE && 75 <= 85? TRUE ← ENTER
Iteration 1:
Pop price: 75
Pop span: 4 ← Inherit 4 days!
span = 1 + 4 = 5
Stack: prices=[100, 80], spans=[1, 1]
Loop check: 80 <= 85? TRUE ← CONTINUE
Iteration 2:
Pop price: 80
Pop span: 1
span = 5 + 1 = 6
Stack: prices=[100], spans=[1]
Loop check: 100 <= 85? FALSE ← EXIT
WHY? 100 > 85, boundary!
Push: prices=[100, 85], spans=[1, 6]
Return: 6 ✓
Stack state:
prices: [100, 85]
spans: [1, 6]
Verification: 85 covered days 1-6 (6 days) ✓
Day 0: 100 > 85, NOT covered ✓
Days 1-6: all <= 85 ✓
Complexity Analysis
⏰ Time: O(1) amortized per call
WHY O(1) even though we have a while loop?
Key insight: Amortized analysis
Each price:
- Pushed to stack: ONCE
- Popped from stack: AT MOST ONCE
If we make n calls total:
- Total pushes: n
- Total pops: n (at most)
- Total operations: 2n
Average per call: 2n / n = 2 = O(1) ✓
Detailed example with 5 calls:
Call 1: push (no pops) → 1 operation
Call 2: push (no pops) → 1 operation
Call 3: push (no pops) → 1 operation
Call 4: pop once, push → 2 operations
Call 5: pop 3 times, push → 4 operations
Total: 1+1+1+2+4 = 9 operations for 5 calls
Average: 9/5 = 1.8 ≈ O(1) per call ✓
The key: Even though one call might pop many times,
those elements were pushed in earlier calls.
Total pops can never exceed total pushes!
💾 Space: O(n)
Worst case: Strictly decreasing prices [100, 99, 98, ..., 1]
Every price stays in stack
All n prices stored
Best case: Strictly increasing prices [1, 2, 3, ..., 100]
Each new price pops all previous
Stack size = 1
Average: Somewhere in between
📊 Approach Comparison
┌────────────────────────────────────────────────────────┐
│ Approach 1 Approach 2 │
│ (Brute Force) (Monotonic Stack) │
├────────────────────────────────────────────────────────┤
│ Core Idea Store all Store (price, span) │
│ prices, scan with stack │
│ │
│ Per Call O(n) O(1) amortized ✓ │
│ Time Scan backward Pop/push once │
│ │
│ Total O(n²) for n O(n) for n calls ✓ │
│ Time calls │
│ │
│ Space O(n) O(n) │
│ All prices Stack (worst case) │
│ │
│ When to Never! Always! ✓ │
│ use Too slow │
└────────────────────────────────────────────────────────┘
🧪 Edge Cases
Edge Case 1: All Same Price
Calls: next(50), next(50), next(50)
Call 1: return 1
Call 2: 50 <= 50? YES, pop (50,1), span=1+1=2, return 2
Call 3: 50 <= 50? YES, pop (50,2), span=1+2=3, return 3
All prices equal → each spans everything before it
Edge Case 2: Strictly Increasing
Calls: next(10), next(20), next(30)
Call 1: return 1
Call 2: 10 <= 20? YES, pop, span=2, return 2
Call 3: 20 <= 30? YES, pop (20,2), span=1+2=3, return 3
Each new price pops ALL previous → linear growth
Edge Case 3: Strictly Decreasing
Calls: next(100), next(90), next(80)
Call 1: return 1
Call 2: 100 <= 90? NO, return 1
Call 3: 90 <= 80? NO, return 1
Each price hits immediate boundary → all spans = 1
Stack grows: [100, 90, 80]
Edge Case 4: Single Call
Call: next(100)
No previous prices → span = 1
Edge Case 5: Alternating High-Low
Calls: next(100), next(50), next(100), next(50)
Call 1: return 1, stack=[(100,1)]
Call 2: 100 > 50, return 1, stack=[(100,1),(50,1)]
Call 3: 50 <= 100, pop, span=2, return 2, stack=[(100,1),(100,2)]
Wait, 100 <= 100? YES, pop, span=2+1=3, return 3
Stack=[(100,3)]
Call 4: 100 > 50, return 1, stack=[(100,3),(50,1)]
⚠️ Common Mistakes
Mistake 1: Not accumulating spans
// ❌ WRONG - Only popping, not adding spans
while (!prices.isEmpty() && prices.peek() <= price) {
prices.pop();
spans.pop(); // Threw away the span!
}
span = 1; // Lost the telescoping!
// ✓ CORRECT - Accumulate spans
while (!prices.isEmpty() && prices.peek() <= price) {
prices.pop();
span += spans.pop(); // Add to our span!
}
Mistake 2: Using < instead of <=
// ❌ WRONG - Strict inequality
while (!prices.isEmpty() && prices.peek() < price) {
// Won't pop equal prices!
// But equal price should be covered!
}
// ✓ CORRECT - Less than or equal
while (!prices.isEmpty() && prices.peek() <= price) {
// Pops equal prices too ✓
}
Mistake 3: Starting span at 0
// ❌ WRONG
int span = 0;
// When no pops happen, span stays 0
// But should be 1 (today itself!)
// ✓ CORRECT
int span = 1; // Count today
Mistake 4: Forgetting to push after popping
// ❌ WRONG
while (...) {
prices.pop();
span += spans.pop();
}
return span; // Didn't push current price!
// Lost this price for future calls!
// ✓ CORRECT
while (...) {
prices.pop();
span += spans.pop();
}
prices.push(price); // Store for future!
spans.push(span);
return span;
Mistake 5: Not checking isEmpty()
// ❌ WRONG - Could throw EmptyStackException
while (prices.peek() <= price) {
prices.pop();
}
// ✓ CORRECT
while (!prices.isEmpty() && prices.peek() <= price) {
prices.pop();
}
🎯 Pattern Recognition
This pattern appears when:
- Finding "previous greater/smaller" element
- Streaming/online data (can't look ahead)
- Need to track ranges/spans going backward
- Consecutive element counting
Key Indicators:
- "Consecutive days"
- "Going backward"
- "Previous element that..."
- "How many before..."
- Online/streaming context
Similar Problems: - Daily Temperatures (opposite direction) - Next Greater Element I/II (forward version) - Sliding Window Maximum - Largest Rectangle in Histogram (uses similar stack)
📝 Quick Revision Notes
🎯 Core Concept
Count consecutive days backward where price <= today's price. Use monotonic stack storing (price, span) pairs. Stack maintains decreasing prices. When new price arrives, pop smaller/equal prices and accumulate their spans (telescoping!). Each price pushed/popped once → O(1) amortized.
⚡ Quick Implementation
import java.util.Arrays;
import java.util.Stack;
import javax.xml.transform.stax.StAXResult;
class Stock {
int price;
int span; // number of days you will need to wait till you find a stock greater than or equal to the current price.
public Stock(int price, int span) {
this.price = price;
this.span = span;
}
}
class StockSpanner {
Stack<Stock> stack;
public StockSpanner() {
stack = new Stack<>();
}
public int next(int price) {
int span = 1;
if(stack.isEmpty()) {
stack.push(new Stock(price, 1)); // default span is 1.
} else if(stack.peek().price > price) {
// current is greater than top. Hence, span is 1 here also.
stack.push(new Stock(price, 1));
} else {
// Pop till we find current is greater than all prev stack elements.
// calculate accumulated span.
// in [100,80,60,70,60,75,85]
// For 100,80,60 => span is 1 as all incoming elements found stak top greater.
// Stack: (100,1),(80,1),(60,1)
// Now, 70 comes
// pop (60,1) => span = 2
// Try to pop (80,1) => cannot
// Stack now: (100,1),(80,1),(70,2)
// Next comes 60 which has span 1 as 60 < 70 (immediate top)
// Stack now: (100,1),(80,1),(70,2),(60,1)
// Next comes 75. Pop till (70,2). Span = 1 + 1 (from 60) + 2 (from 70) = 4
// Stack now: (100,1),(80,1),(75,4)
// Next comes 85. Pop till (80,1). Span = 1 + 4 (from 75) + 1 (from 80) = 6
// Stack now: (100,1),(85,6)
// So, for example, (75,4) tells that current value (85) is still greater than 75
// and you will find next value greater than 75 before 4 days only (60,70,60,80). Hence, add them.
// This is kind of ACCUMULATION
while (!stack.isEmpty() && stack.peek().price <= price) {
Stock poppedStock = stack.pop();
span = span + poppedStock.span;
}
stack.push(new Stock(price, span));
}
return span;
}
}
class Solution {
public static void main(String[] args) {
Solution s = new Solution();
StockSpanner ss = new StockSpanner();
System.out.println(ss.next(100)); // return 1
System.out.println(ss.next(80)); // return 1
System.out.println(ss.next(60)); // return 1
System.out.println(ss.next(70)); // return 2
System.out.println(ss.next(60)); // return 1
System.out.println(ss.next(75)); // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
System.out.println(ss.next(85)); // return 6
}
}
🔑 Key Insights
Why (price, span) pairs?
Need span to know how many days each price covered
When we pop, we inherit those days!
This is the telescoping optimization!
The Telescoping Magic:
If we pop (70, 2):
- 70 covered 2 days
- Current price >= 70
- Current also covers those 2 days
- Add 2 to span!
No need to check those 2 days individually!
Time Complexity Proof:
n calls total:
- Each price pushed: once (n pushes)
- Each price popped: at most once (≤n pops)
- Total ops: ≤2n
- Per call: 2n/n = 2 = O(1) amortized ✓
Stack Invariant:
Prices always STRICTLY DECREASING (top to bottom)
Why? Pop all <= before pushing new
Result: Clean boundaries for future queries
🎪 Memory Aid
"Store (price, SPAN) not just price!"
"Pop smaller → ACCUMULATE their spans!"
"Each price pushed ONCE, popped ONCE!"
"Telescoping = skip entire ranges!" ✨
⚠️ Don't Forget
- Start span at 1 (today counts!)
- Use <= not < (equal prices covered!)
- Accumulate spans when popping (span += ...)
- Check !isEmpty() before peek/pop
- Push current (price, span) after popping
- Amortized O(1), not worst-case!
🔗 Connection to Other Problems
Daily Temperatures: Next greater FORWARD
Stock Span: Previous greater BACKWARD
Same pattern, opposite direction!
Both use monotonic stack with similar logic.
Happy coding! This is a beautiful example of amortized analysis and the power of storing accumulated information! 🚀