Range query problems—finding properties of ranges or subarrays—often seem to require O(n²) nested loops. But monotonic stacks can optimize many of them to O(n).
The key insight: Instead of asking "what's the property of this range?", ask "for which ranges does this element determine the property?" This reversal of perspective unlocks the O(n) solution.
This comprehensive guide will teach you how monotonic stacks solve range queries, the stock span pattern, trapping rain water, and when to store indices vs values.
Monotonic stack for range queries:
Key technique: For each element, find the range where it's relevant (min, max, or boundary)
Time: O(n), Space: O(n)
The stock span for a given day is the maximum number of consecutive days (including today) where the stock price was less than or equal to today's price.
Example:
Prices: [100, 80, 60, 70, 60, 75, 85]
Spans: [1, 1, 1, 2, 1, 4, 6]
Explanation:
- Day 0 (100): No previous days, span = 1
- Day 1 (80): 80 < 100, span = 1
- Day 2 (60): 60 < 80, span = 1
- Day 3 (70): 70 > 60, span = 2 (includes day 2)
- Day 4 (60): 60 < 70, span = 1
- Day 5 (75): 75 > 60, 70, 60, span = 4 (includes days 2,3,4)
- Day 6 (85): 85 > all previous, span = 6 (includes days 0-5)def stock_span_brute(prices):
"""
For each day, scan backward to count consecutive days.
Time: O(n²)
Space: O(1)
"""
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 spansTime complexity: O(n²) in worst case (strictly increasing prices)
Insight: Use a decreasing stack to track potential "span boundaries."
Key observation: If today's price is higher than yesterday's, we can "absorb" yesterday's span.
class StockSpanner:
"""
LeetCode #901: Online Stock Span
Approach: Monotonic decreasing stack
- Stack stores (price, span) pairs
- When new price arrives, pop all smaller prices and accumulate spans
Time: O(1) amortized per call
Space: O(n) worst case
"""
def __init__(self):
self.stack = [] # (price, span)
def next(self, price):
span = 1 # Start with today
# Pop all smaller or equal prices
while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1] # Accumulate their spans
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)) # 6Visual trace:
Prices: [100, 80, 60, 70, 60, 75, 85]
Day 0, price=100:
stack=[], span=1
stack=[(100,1)]
Day 1, price=80:
80 < 100, don't pop
span=1
stack=[(100,1), (80,1)]
Day 2, price=60:
60 < 80, don't pop
span=1
stack=[(100,1), (80,1), (60,1)]
Day 3, price=70:
70 > 60, pop (60,1), span=1+1=2
70 < 80, stop
stack=[(100,1), (80,1), (70,2)]
Day 4, price=60:
60 < 70, don't pop
span=1
stack=[(100,1), (80,1), (70,2), (60,1)]
Day 5, price=75:
75 > 60, pop (60,1), span=1+1=2
75 > 70, pop (70,2), span=2+2=4
75 < 80, stop
stack=[(100,1), (80,1), (75,4)]
Day 6, price=85:
85 > 75, pop (75,4), span=1+4=5
85 > 80, pop (80,1), span=5+1=6
85 < 100, stop
stack=[(100,1), (85,6)]
Final spans: [1, 1, 1, 2, 1, 4, 6] ✓Key insight: When we pop a price, we "absorb" its span because all those days are also ≤ current price.
Time: O(1) amortized per call
Space: O(n) worst case (strictly decreasing prices)
Given heights of bars, calculate how much water can be trapped after raining.
Example:
Heights: [0,1,0,2,1,0,1,3,2,1,2,1]
Visual:
█
█ ██ █
█ ██ ███████
0120101321 21
Water trapped: 6 unitsInsight: Water is trapped in "valleys" between bars. Use stack to find valleys.
def trap_stack(height):
"""
LeetCode #42: Trapping Rain Water
Approach: Monotonic increasing stack
- Stack stores indices of bars
- When we find a taller bar, calculate water trapped
Time: O(n)
Space: O(n)
"""
if not height:
return 0
water = 0
stack = [] # Store indices, maintain increasing heights
for i in range(len(height)):
# When current bar is taller, we found a right boundary
while stack and height[i] > height[stack[-1]]:
bottom = stack.pop() # This is the valley bottom
if not stack:
break # No left boundary
# Calculate trapped water
left_boundary = stack[-1]
right_boundary = i
width = right_boundary - left_boundary - 1
bounded_height = min(height[left_boundary], height[right_boundary]) - height[bottom]
water += width * bounded_height
stack.append(i)
return water
# Example
print(trap_stack([0,1,0,2,1,0,1,3,2,1,2,1]))
# Output: 6Heights: [0,1,0,2,1,0,1,3,2,1,2,1]
[0 1 2 3 4 5 6 7 8 9 10 11]
i=0, h=0: stack=[0]
i=1, h=1: 1 > 0, pop 0, no left boundary, stack=[1]
i=2, h=0: 0 < 1, stack=[1,2]
i=3, h=2:
2 > 0, pop 2 (bottom), left=1, right=3
width = 3-1-1 = 1
height = min(1,2) - 0 = 1
water = 1×1 = 1
2 > 1, pop 1, no left boundary
stack=[3]
Total water: 1
i=4, h=1: 1 < 2, stack=[3,4]
i=5, h=0: 0 < 1, stack=[3,4,5]
i=6, h=1:
1 > 0, pop 5, left=4, right=6
width = 6-4-1 = 1
height = min(1,1) - 0 = 1
water = 1×1 = 1
1 = 1, stop
stack=[3,4,6]
Total water: 2
i=7, h=3:
3 > 1, pop 6, left=4, right=7
width = 7-4-1 = 2
height = min(1,3) - 1 = 0
water = 2×0 = 0
3 > 1, pop 4, left=3, right=7
width = 7-3-1 = 3
height = min(2,3) - 1 = 1
water = 3×1 = 3
3 > 2, pop 3, no left boundary
stack=[7]
Total water: 5
i=8, h=2: 2 < 3, stack=[7,8]
i=9, h=1: 1 < 2, stack=[7,8,9]
i=10, h=2:
2 > 1, pop 9, left=8, right=10
width = 10-8-1 = 1
height = min(2,2) - 1 = 1
water = 1×1 = 1
2 = 2, stop
stack=[7,8,10]
Total water: 6
i=11, h=1: 1 < 2, stack=[7,8,10,11]
Final water: 6 ✓For comparison, here's the two-pointer approach:
def trap_two_pointers(height):
"""
Alternative: Two pointers approach
Time: O(n)
Space: O(1) ← Better space complexity
"""
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return waterComparison:
See detailed guide: Trapping Rain Water Edge Cases
Find the maximum j - i such that i < j and nums[i] <= nums[j].
Example:
Input: nums = [6,0,8,2,1,5]
Output: 4
Explanation: i=1, j=5, nums[1]=0 <= nums[5]=5, width=5-1=4def maxWidthRamp(nums):
"""
LeetCode #962: Maximum Width Ramp
Approach:
1. Build decreasing stack of indices (potential left boundaries)
2. Scan right to left, find maximum width
Time: O(n)
Space: O(n)
"""
n = len(nums)
stack = []
# Build decreasing stack (potential left boundaries)
for i in range(n):
if not stack or nums[i] < nums[stack[-1]]:
stack.append(i)
max_width = 0
# Scan right to left to find maximum width
for j in range(n - 1, -1, -1):
while stack and nums[j] >= nums[stack[-1]]:
i = stack.pop()
max_width = max(max_width, j - i)
return max_width
# Example
print(maxWidthRamp([6,0,8,2,1,5]))
# Output: 4Why it works:
Remove k digits from a number to make it the smallest possible.
Example:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove 4, 3, 2 to get 1219def removeKdigits(num, k):
"""
LeetCode #402: Remove K Digits
Approach: Greedy + monotonic increasing stack
- Maintain increasing digits
- Remove larger digits when we see smaller
Time: O(n)
Space: O(n)
"""
stack = []
for digit in num:
# Remove larger digits (make number smaller)
while stack and k > 0 and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# If k > 0, remove from end
if k > 0:
stack = stack[:-k]
# Remove leading zeros and convert to string
result = ''.join(stack).lstrip('0')
return result if result else '0'
# Example
print(removeKdigits("1432219", 3))
# Output: "1219"Why it works:
✅ Need to calculate distances
j - i✅ Need to access original array
height[stack[-1]]✅ Need to track positions
Example:
stack = [] # Store indices
for i in range(n):
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = i - idx # Calculate distance
stack.append(i)✅ Only need comparisons
✅ Don't need distances or positions
✅ Simpler implementation
Example:
stack = [] # Store values
for digit in num:
while stack and stack[-1] > digit:
stack.pop()
stack.append(digit)Do you need distances (j - i)?
├─ YES → Store indices
└─ NO → Continue
Do you need to access original array?
├─ YES → Store indices
└─ NO → Continue
Do you need position information?
├─ YES → Store indices
└─ NO → Store values (simpler)See detailed guide: Indices vs Values
❌ Wrong:
# Using increasing stack
while stack and stack[-1][0] >= price: # Wrong!
stack.pop()✅ Correct:
# Use decreasing stack
while stack and stack[-1][0] <= price: # Correct
span += stack.pop()[1]❌ Wrong:
while stack and height[i] > height[stack[-1]]:
bottom = stack.pop()
# Assume left boundary exists
left = stack[-1] # Can crash if stack is empty!✅ Correct:
while stack and height[i] > height[stack[-1]]:
bottom = stack.pop()
if not stack:
break # No left boundary
left = stack[-1]❌ Wrong:
width = right - left # Off by one!✅ Correct:
width = right - left - 1 # Exclude boundariesAll patterns use amortized O(n):
Stack can grow to size n in worst case.
Master range queries with monotonic stack:
Monotonic stacks optimize range query problems by reversing the question: instead of "what's the property of this range?", ask "for which ranges does this element determine the property?"
Key patterns:
When to store indices vs values:
Time complexity: O(n) through amortized analysis
Space complexity: O(n) for stack storage
Master these patterns, and you'll solve complex range query problems with elegance.
Next steps:
Next time you see a range query problem, ask: "Can I use a monotonic stack to optimize this?"
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.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free