LeetCode Pattern/Monotonic Stack & Queue/Stock Span Problem: Complete Solution with Monotonic Stack

Stock Span Problem: Complete Solution with Monotonic Stack

LeetCopilot Team

Dec 22, 2025

12 min read

Monotonic StackStock SpanLeetCode 901Interview PrepAlgorithm Walkthrough

Master the stock span problem with a complete walkthrough, visual examples, and edge case handling. Understand why monotonic decreasing stack is the optimal solution.

Complete Guide

The Complete Monotonic Stack & Queue Guide: Master All Patterns, Templates, and Techniques

The ultimate comprehensive guide to monotonic stacks and queues. Learn all variants, when to use each pattern, complete templates in multiple languages, and a systematic approach to solve any monotonic stack/queue problem.

Read the complete guide

The stock span problem is a classic monotonic stack application that appears frequently in interviews. It's elegant, practical, and perfectly demonstrates why monotonic stacks are powerful.

But here's what trips up most developers: understanding why we can "absorb" previous spans and how the stack maintains the right information.

This guide will give you a complete understanding of the stock span problem, step-by-step solution, visual examples, and edge case handling.

TL;DR

Problem: For each day, find the maximum number of consecutive days (including today) where the stock price was ≤ today's price.

Solution: Monotonic decreasing stack storing (price, span) pairs

Time: O(1) amortized per day, Space: O(n)

Key insight: When today's price is higher than yesterday's, we can "absorb" yesterday's span because all those days are also ≤ today's price.

Problem Definition

Stock Span

The stock span for a given day is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to the price on that day.

Formal definition:

code

span[i] = max number of consecutive days ending at i 
          where price[j] <= price[i] for all j in range

Example 1: Basic Case

code

Prices: [100, 80, 60, 70, 60, 75, 85]
Days:   [0,   1,  2,  3,  4,  5,  6]

Spans:  [1,   1,  1,  2,  1,  4,  6]

Explanation:
Day 0 (100): No previous days → span = 1
Day 1 (80):  80 < 100 → span = 1 (only today)
Day 2 (60):  60 < 80 → span = 1 (only today)
Day 3 (70):  70 > 60, 70 < 80 → span = 2 (days 2,3)
Day 4 (60):  60 < 70 → span = 1 (only today)
Day 5 (75):  75 > 60,70,60, 75 < 80 → span = 4 (days 2,3,4,5)
Day 6 (85):  85 > all previous except 100 → span = 6 (days 1-6)

Example 2: Strictly Increasing

code

Prices: [10, 20, 30, 40, 50]
Spans:  [1,  2,  3,  4,  5]

Each day's price is higher than all previous days.

Example 3: Strictly Decreasing

code

Prices: [50, 40, 30, 20, 10]
Spans:  [1,  1,  1,  1,  1]

Each day's price is lower than all previous days.

Brute Force Solution: O(n²)

Implementation

python

def stock_span_brute_force(prices):
    """
    For each day, scan backward to count consecutive days.
    
    Time: O(n²)
    Space: O(1) (excluding output)
    """
    n = len(prices)
    spans = []
    
    for i in range(n):
        span = 1  # Include today
        j = i - 1
        
        # Count consecutive days with price <= today
        while j >= 0 and prices[j] <= prices[i]:
            span += 1
            j -= 1
        
        spans.append(span)
    
    return spans

# Example
prices = [100, 80, 60, 70, 60, 75, 85]
print(stock_span_brute_force(prices))
# Output: [1, 1, 1, 2, 1, 4, 6]

Time Complexity Analysis

Best case: O(n) - strictly decreasing prices

Each day only counts itself
Inner loop never executes

Worst case: O(n²) - strictly increasing prices

Day 0: 0 comparisons
Day 1: 1 comparison
Day 2: 2 comparisons
...
Day n-1: n-1 comparisons
Total: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²)

Average case: O(n²)

Monotonic Stack Solution: O(n)

The Key Insight

Observation: If today's price is higher than yesterday's, we don't need to check the days before yesterday individually. We can "absorb" yesterday's entire span.

Why? If yesterday's span was 3 (meaning the 3 days before yesterday all had price ≤ yesterday's price), and today's price > yesterday's price, then all those 3 days also have price ≤ today's price.

Visual:

code

Prices: [60, 70, 75]
        [i-2 i-1 i]

If price[i-1] = 70 has span = 2 (includes i-2 and i-1)
And price[i] = 75 > 70
Then price[i] > price[i-1] >= price[i-2]
So span[i] can absorb span[i-1]

Implementation

python

class StockSpanner:
    """
    LeetCode #901: Online Stock Span
    
    Approach: Monotonic decreasing stack
    - Stack stores (price, span) pairs
    - Maintain decreasing order of prices
    - When new price arrives, pop smaller prices and accumulate spans
    
    Time: O(1) amortized per next() call
    Space: O(n) worst case
    """
    def __init__(self):
        self.stack = []  # (price, span)
    
    def next(self, price):
        """
        Calculate span for the new price.
        
        Args:
            price: Today's stock price
        
        Returns:
            Span for today
        """
        span = 1  # Start with today
        
        # Pop all prices <= current price
        # Absorb their spans
        while self.stack and self.stack[-1][0] <= price:
            prev_price, prev_span = self.stack.pop()
            span += prev_span
        
        # Push current price and its span
        self.stack.append((price, span))
        
        return span

# Usage
spanner = StockSpanner()
print(spanner.next(100))  # 1
print(spanner.next(80))   # 1
print(spanner.next(60))   # 1
print(spanner.next(70))   # 2
print(spanner.next(60))   # 1
print(spanner.next(75))   # 4
print(spanner.next(85))   # 6

Complete Step-by-Step Trace

code

Prices: [100, 80, 60, 70, 60, 75, 85]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Day 0: price = 100
  Stack: []
  span = 1 (no previous days)
  Push (100, 1)
  Stack: [(100, 1)]
  Return: 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Day 1: price = 80
  Stack: [(100, 1)]
  span = 1
  80 < 100, don't pop
  Push (80, 1)
  Stack: [(100, 1), (80, 1)]
  Return: 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Day 2: price = 60
  Stack: [(100, 1), (80, 1)]
  span = 1
  60 < 80, don't pop
  Push (60, 1)
  Stack: [(100, 1), (80, 1), (60, 1)]
  Return: 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Day 3: price = 70
  Stack: [(100, 1), (80, 1), (60, 1)]
  span = 1
  
  70 > 60, pop (60, 1)
    span = 1 + 1 = 2
  
  70 < 80, stop
  Push (70, 2)
  Stack: [(100, 1), (80, 1), (70, 2)]
  Return: 2

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Day 4: price = 60
  Stack: [(100, 1), (80, 1), (70, 2)]
  span = 1
  60 < 70, don't pop
  Push (60, 1)
  Stack: [(100, 1), (80, 1), (70, 2), (60, 1)]
  Return: 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Day 5: price = 75
  Stack: [(100, 1), (80, 1), (70, 2), (60, 1)]
  span = 1
  
  75 > 60, pop (60, 1)
    span = 1 + 1 = 2
  
  75 > 70, pop (70, 2)
    span = 2 + 2 = 4
  
  75 < 80, stop
  Push (75, 4)
  Stack: [(100, 1), (80, 1), (75, 4)]
  Return: 4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Day 6: price = 85
  Stack: [(100, 1), (80, 1), (75, 4)]
  span = 1
  
  85 > 75, pop (75, 4)
    span = 1 + 4 = 5
  
  85 > 80, pop (80, 1)
    span = 5 + 1 = 6
  
  85 < 100, stop
  Push (85, 6)
  Stack: [(100, 1), (85, 6)]
  Return: 6

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Final spans: [1, 1, 1, 2, 1, 4, 6] ✓

Why the Stack is Decreasing

Invariant: Stack maintains decreasing order of prices (bottom to top).

Why? When we encounter a higher price, we pop all smaller or equal prices. This ensures that only prices that are strictly greater than the current price remain in the stack.

Visual:

code

After processing [100, 80, 60, 70]:
Stack: [(100, 1), (80, 1), (70, 2)]
       
Prices: 100 > 80 > 70  ← Decreasing ✓

Why It's O(n)

Amortized Analysis

Each price is:

Pushed to the stack exactly once
Popped from the stack at most once

Total operations:

n pushes (one per price)
At most n pops (each price popped at most once)
Total: 2n = O(n)

Amortized cost per price: O(n) / n = O(1)

Visual Proof

code

Prices: [100, 80, 60, 70, 60, 75, 85]

Operations:
Day 0: Push 100                    (1 op)
Day 1: Push 80                     (1 op)
Day 2: Push 60                     (1 op)
Day 3: Pop 60, Push 70             (2 ops)
Day 4: Push 60                     (1 op)
Day 5: Pop 60, Pop 70, Push 75     (3 ops)
Day 6: Pop 75, Pop 80, Push 85     (3 ops)

Total: 12 operations for 7 prices
Average: 12/7 ≈ 1.7 ops per price
Complexity: O(1) amortized

Edge Cases

Edge Case 1: Single Price

python

spanner = StockSpanner()
print(spanner.next(100))  # 1
# Stack: [(100, 1)]

Edge Case 2: All Same Prices

python

spanner = StockSpanner()
print(spanner.next(50))  # 1
print(spanner.next(50))  # 2
print(spanner.next(50))  # 3
print(spanner.next(50))  # 4

# Each price absorbs all previous equal prices

Edge Case 3: Strictly Increasing

python

spanner = StockSpanner()
print(spanner.next(10))  # 1
print(spanner.next(20))  # 2
print(spanner.next(30))  # 3
print(spanner.next(40))  # 4
print(spanner.next(50))  # 5

# Each price absorbs all previous prices
# Stack always has one element

Edge Case 4: Strictly Decreasing

python

spanner = StockSpanner()
print(spanner.next(50))  # 1
print(spanner.next(40))  # 1
print(spanner.next(30))  # 1
print(spanner.next(20))  # 1
print(spanner.next(10))  # 1

# No price is absorbed
# Stack grows to size 5

Edge Case 5: Large Price After Many Small Prices

python

spanner = StockSpanner()
for i in range(100):
    print(spanner.next(10))  # All return 1
print(spanner.next(1000))    # Returns 101

# One large price absorbs all previous prices
# Stack size goes from 100 to 1

Common Mistakes

Mistake 1: Using Increasing Stack

❌ Wrong:

python

# Maintaining increasing order
while self.stack and self.stack[-1][0] >= price:
    self.stack.pop()
# This doesn't accumulate spans correctly!

✅ Correct:

python

# Maintaining decreasing order
while self.stack and self.stack[-1][0] <= price:
    span += self.stack.pop()[1]

Mistake 2: Not Accumulating Spans

❌ Wrong:

python

while self.stack and self.stack[-1][0] <= price:
    self.stack.pop()  # Forgot to accumulate span!

✅ Correct:

python

while self.stack and self.stack[-1][0] <= price:
    span += self.stack.pop()[1]  # Accumulate span

Mistake 3: Storing Only Prices

❌ Wrong:

python

self.stack.append(price)  # Lost span information!

✅ Correct:

python

self.stack.append((price, span))  # Store both

Mistake 4: Wrong Comparison (< instead of <=)

❌ Wrong:

python

while self.stack and self.stack[-1][0] < price:
    span += self.stack.pop()[1]
# Doesn't handle equal prices correctly!

✅ Correct:

python

while self.stack and self.stack[-1][0] <= price:
    span += self.stack.pop()[1]
# Handles equal prices

Alternative: Storing Indices

Implementation with Indices

python

class StockSpanner:
    """
    Alternative: Store indices instead of spans.
    
    Trade-off: Simpler logic, but need to store prices separately.
    """
    def __init__(self):
        self.prices = []
        self.stack = []  # Store indices
    
    def next(self, price):
        self.prices.append(price)
        current_index = len(self.prices) - 1
        
        # Pop all indices with price <= current
        while self.stack and self.prices[self.stack[-1]] <= price:
            self.stack.pop()
        
        # Calculate span
        if not self.stack:
            span = current_index + 1  # All previous days
        else:
            span = current_index - self.stack[-1]
        
        self.stack.append(current_index)
        return span

Comparison:

Storing (price, span): More direct, no need for separate prices array
Storing indices: Simpler span calculation, but need extra array

Complexity Summary

Approach	Time per call	Space	Notes
Brute Force	O(n) worst	O(1)	Simple but slow
Monotonic Stack	O(1) amortized	O(n)	Optimal

Space complexity detail:

Best case: O(1) - strictly increasing prices (stack size = 1)
Worst case: O(n) - strictly decreasing prices (stack size = n)
Average case: O(log n) - random prices

Practice Variants

Similar problems to practice:

Online Stock Span (#901) - The canonical problem
Daily Temperatures (#739) - Similar pattern, find next warmer day
Next Greater Element I (#496) - Find next greater element
Buildings With Ocean View (#1762) - Visibility problem

Conclusion

The stock span problem is a perfect demonstration of monotonic stack power.

Key insights:

Absorb spans: When price is higher, absorb previous spans
Decreasing stack: Maintain decreasing order of prices
O(1) amortized: Each price pushed and popped at most once
Store (price, span): Need both for span accumulation

The algorithm:

python

span = 1
while stack and stack[-1][0] <= price:
    span += stack.pop()[1]
stack.append((price, span))
return span

Why it works:

Popping smaller prices and accumulating their spans
Ensures we count all consecutive days with price ≤ today

Master this problem, and you'll understand the core principle of monotonic stacks.

Next steps:

Next time you see "consecutive days" or "span," reach for the monotonic stack.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot

Add to Chrome for free

Also compatible with Edge, Brave, and Opera

Stock Span Problem: Complete Solution with Monotonic Stack

The Complete Monotonic Stack & Queue Guide: Master All Patterns, Templates, and Techniques

Table of Contents

TL;DR

Problem Definition

Stock Span

Example 1: Basic Case

Example 2: Strictly Increasing

Example 3: Strictly Decreasing

Brute Force Solution: O(n²)

Implementation

Time Complexity Analysis

Monotonic Stack Solution: O(n)

The Key Insight

Implementation

Complete Step-by-Step Trace

Why the Stack is Decreasing

Why It's O(n)

Amortized Analysis

Visual Proof

Edge Cases

Edge Case 1: Single Price

Edge Case 2: All Same Prices

Edge Case 3: Strictly Increasing

Edge Case 4: Strictly Decreasing

Edge Case 5: Large Price After Many Small Prices

Common Mistakes

Mistake 1: Using Increasing Stack

Mistake 2: Not Accumulating Spans

Mistake 3: Storing Only Prices

Mistake 4: Wrong Comparison (< instead of <=)

Alternative: Storing Indices

Implementation with Indices

Complexity Summary

Practice Variants

Conclusion

Want to Practice LeetCode Smarter?

Related Tutorials

Why Your Monotonic Stack Fails on Duplicates (And How to Fix It)

5 Common Mistakes in Next Greater Element Problems (And How to Avoid Them)

3 Critical Mistakes in Largest Rectangle in Histogram (And How to Fix Them)