Monotonic Stack: Next Greater Element Problems
A monotonic stack is a stack that maintains its elements in either strictly increasing or strictly decreasing order from bottom to top. When you push a new element, you first pop all elements that...
Key Insights
- Monotonic stacks reduce “next greater/smaller element” problems from O(n²) brute force to O(n) by maintaining elements in sorted order and processing each element exactly once
- The key insight is that when you find a greater element, it’s the answer for all smaller elements currently on the stack—pop them all and record the result
- Use a decreasing stack for “next greater” problems and an increasing stack for “next smaller” problems; store indices rather than values to handle position-based queries
Introduction to Monotonic Stacks
A monotonic stack is a stack that maintains its elements in either strictly increasing or strictly decreasing order from bottom to top. When you push a new element, you first pop all elements that would violate this ordering. This simple invariant turns out to be remarkably powerful for a specific class of problems: finding the next greater (or smaller) element for each position in an array.
The brute force approach to “next greater element” is straightforward—for each element, scan rightward until you find something larger. This gives O(n²) time complexity. The monotonic stack approach processes each element at most twice (one push, one pop), achieving O(n) time.
This pattern appears constantly in interview problems and real-world scenarios: stock price analysis, temperature forecasting, histogram calculations, and sliding window maximums. Master this technique and you’ll recognize it immediately when it applies.
How Monotonic Stacks Work
The core invariant is simple: before pushing an element, pop everything that violates the monotonic property. For a decreasing stack, pop all elements smaller than the incoming element. For an increasing stack, pop all elements larger.
Here’s how the stack evolves for array [2, 1, 5, 6, 2, 3] with a decreasing stack:
Process 2: Stack empty, push 2 → Stack: [2]
Process 1: 1 < 2, push 1 → Stack: [2, 1]
Process 5: 5 > 1, pop 1 (next greater of 1 is 5)
5 > 2, pop 2 (next greater of 2 is 5)
Push 5 → Stack: [5]
Process 6: 6 > 5, pop 5 (next greater of 5 is 6)
Push 6 → Stack: [6]
Process 2: 2 < 6, push 2 → Stack: [6, 2]
Process 3: 3 > 2, pop 2 (next greater of 2 is 3)
Push 3 → Stack: [6, 3]
End: 6 and 3 have no next greater element
The magic happens during the pop operation. When element X causes element Y to be popped, X is definitively the next greater element for Y. Everything between Y and X in the original array was smaller than Y (otherwise Y would have been popped earlier), so X is the first element greater than Y.
Here’s the basic template:
def monotonic_decreasing_stack_template(nums):
"""
Template for maintaining a monotonic decreasing stack.
Stack holds indices, not values—this is almost always what you want.
"""
n = len(nums)
result = [-1] * n # Default: no next greater element
stack = [] # Stores indices
for i in range(n):
# Pop all elements smaller than current
while stack and nums[stack[-1]] < nums[i]:
popped_index = stack.pop()
result[popped_index] = nums[i] # or i, depending on what you need
stack.append(i)
return result
When to use which stack:
- Decreasing stack: Finding next greater element (elements pop when something larger arrives)
- Increasing stack: Finding next smaller element (elements pop when something smaller arrives)
Classic Problem: Next Greater Element I
Let’s solve the foundational problem: given an array, for each element find the next element to its right that is strictly greater. Return -1 if none exists.
def next_greater_element(nums):
"""
For each element, find the next greater element to its right.
Example:
Input: [2, 1, 2, 4, 3]
Output: [4, 2, 4, -1, -1]
Explanation:
- 2 → next greater is 4
- 1 → next greater is 2
- 2 → next greater is 4
- 4 → no greater element to the right
- 3 → no greater element to the right
"""
n = len(nums)
result = [-1] * n
stack = [] # Monotonic decreasing stack of indices
for i in range(n):
# Current element is the "next greater" for all smaller elements on stack
while stack and nums[stack[-1]] < nums[i]:
smaller_index = stack.pop()
result[smaller_index] = nums[i]
stack.append(i)
# Elements remaining in stack have no next greater element
# They already have -1 from initialization
return result
Let’s trace through [2, 1, 2, 4, 3]:
i=0, nums[i]=2: Stack empty, push 0 → Stack: [0]
i=1, nums[i]=1: 1 < nums[0]=2, push 1 → Stack: [0, 1]
i=2, nums[i]=2: 2 > nums[1]=1, pop 1, result[1]=2
2 = nums[0]=2 (not greater), push 2 → Stack: [0, 2]
i=3, nums[i]=4: 4 > nums[2]=2, pop 2, result[2]=4
4 > nums[0]=2, pop 0, result[0]=4
push 3 → Stack: [3]
i=4, nums[i]=3: 3 < nums[3]=4, push 4 → Stack: [3, 4]
Final result: [4, 2, 4, -1, -1]
Variation: Next Greater Element II (Circular Array)
In a circular array, the element after the last one wraps around to the first. The trick is to iterate through the array twice, simulating the circular nature.
def next_greater_circular(nums):
"""
Circular array: after the last element, we wrap to the beginning.
Example:
Input: [1, 2, 1]
Output: [2, -1, 2]
The last 1 wraps around and finds 2 at the beginning.
"""
n = len(nums)
result = [-1] * n
stack = []
# Iterate twice: indices 0 to 2n-1
# Use modulo to wrap around
for i in range(2 * n):
actual_index = i % n
while stack and nums[stack[-1]] < nums[actual_index]:
popped_index = stack.pop()
result[popped_index] = nums[actual_index]
# Only push during first pass to avoid duplicates
if i < n:
stack.append(i)
return result
The key insight: we only push indices during the first pass (i < n), but we continue popping during the second pass. This ensures each element gets a chance to find its next greater element from the wrapped-around portion.
Practical Applications
Daily Temperatures
Given daily temperatures, find how many days until a warmer day. This is “next greater element” but returning the distance instead of the value.
def daily_temperatures(temperatures):
"""
Return array where result[i] = days until warmer temperature.
Example:
Input: [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
"""
n = len(temperatures)
result = [0] * n
stack = [] # Indices of days waiting for warmer weather
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
prev_day = stack.pop()
result[prev_day] = i - prev_day # Distance, not temperature
stack.append(i)
return result
Stock Span Problem
For each day, find how many consecutive days (including today) the price was less than or equal to today’s price. This is a “previous greater element” problem—we look left instead of right.
def stock_span(prices):
"""
Span = count of consecutive days with price <= today, looking backward.
Example:
Input: [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]
"""
n = len(prices)
result = [0] * n
stack = [] # Indices of potential "previous greater" elements
for i in range(n):
# Pop all days with smaller or equal prices
while stack and prices[stack[-1]] <= prices[i]:
stack.pop()
# Span extends back to the previous greater element (or beginning)
result[i] = i - stack[-1] if stack else i + 1
stack.append(i)
return result
Common Patterns and Edge Cases
Store indices, not values. Almost every problem needs position information—distances, spans, or mapping back to original arrays. Store indices and look up values with nums[stack[-1]].
Handling duplicates. The comparison operator matters:
<for strictly greater (equal elements stay on stack)<=for greater or equal (equal elements get popped)
Choose based on problem requirements.
Left-to-right vs right-to-left. Left-to-right finds “next” greater/smaller. Right-to-left finds “previous” greater/smaller. You can also iterate left-to-right and reframe “previous greater” as “for whom am I the previous greater element?”
Empty stack handling. Always check stack before accessing stack[-1]. An empty stack typically means “no previous/next element exists”—return -1, 0, or the array boundary depending on the problem.
# Safe pattern for "previous greater" problems
previous_greater_index = stack[-1] if stack else -1
Complexity Analysis and When to Use
Time complexity: O(n). Each element is pushed once and popped at most once. The while loop across all iterations processes at most n pops total.
Space complexity: O(n). In the worst case (strictly decreasing input for a decreasing stack), all elements remain on the stack.
Recognition signals:
- “Next greater/smaller element”
- “Days until X happens”
- “Span of consecutive elements”
- “First element to the left/right satisfying condition”
- Histogram problems (largest rectangle)
When NOT to use monotonic stacks:
- Range queries for arbitrary intervals → use segment trees or sparse tables
- Dynamic updates → monotonic stacks are for static arrays
- K-th greater element → different technique needed
The monotonic stack is a specialized tool. When the problem fits the pattern, it’s the cleanest and most efficient solution. Learn to recognize the pattern and you’ll solve these problems in minutes.