23 questions using this pattern
Maintain a stack where elements are always in sorted order (either increasing or decreasing). This enables efficient solutions for "next greater element" problems by leveraging the stack's ability to track candidates that might be the answer for future elements.
Imagine standing in a line of people of varying heights, all facing forward. You want to know who's the next taller person for each person in line. The trick: as you walk backward through the line, keep track of "potentially useful" tall people. When you encounter someone taller than people you're tracking, those shorter people will never be the answer—remove them. The remaining stack always contains candidates in decreasing height order.
Another analogy: a bouncer at a club with height requirements. As people line up, anyone shorter than the person in front can be removed from consideration— they'll never be visible from the front.
A monotonic stack maintains elements in sorted order by popping elements that violate the ordering when pushing new ones:
The key insight is that when we pop an element, we've found its "next greater/smaller"—it's the current element we're about to push. The stack efficiently tracks candidates that might be answers for future elements.
Pattern recognition:
def next_greater_element(nums: list[int]) -> list[int]: n = len(nums) result = [-1] * n stack = [] # stores indices for i in range(n): # Pop all smaller elements - current is their answer while stack and nums[i] > nums[stack[-1]]: idx = stack.pop() result[idx] = nums[i] stack.append(i) return resultGiven array [4, 5, 2, 10, 8], for each element find the next greater element to its right. If none exists, use -1.
Next Greater Element:
Array: [4, 5, 2, 10, 8]
Find next greater element for each
Process right to left (or left to right with index tracking):
Process 8: stack=[] → no greater, push 8
stack=[8] → answer[4] = -1
Process 10: stack=[8] → 10 > 8, pop 8
stack=[] → no greater, push 10
stack=[10] → answer[3] = -1
Process 2: stack=[10] → 2 < 10, don't pop
stack=[10,2] → answer[2] = 10
Process 5: stack=[10,2] → 5 > 2, pop 2
stack=[10] → 5 < 10, don't pop
stack=[10,5] → answer[1] = 10
Process 4: stack=[10,5] → 4 < 5, don't pop
stack=[10,5,4] → answer[0] = 5
Result: [5, 10, 10, -1, -1]
Largest Rectangle in Histogram:
Heights: [2, 1, 5, 6, 2, 3]
Use increasing stack (pop when current < top)
When popping, calculate rectangle with popped height as the smallest bar.
Process each bar:
- 2: push (0,2)
- 1: 1 < 2, pop (0,2) → width=1, area=2×1=2
push (0,1) [take popped index]
- 5: push (2,5)
- 6: push (3,6)
- 2: 2 < 6, pop (3,6) → width=1, area=6×1=6
2 < 5, pop (2,5) → width=2, area=5×2=10
push (2,2)
- 3: push (5,3)
- end: pop remaining, calculate areas
Max area = 10
Use this skeleton as a starting point for problems using this pattern:
def next_greater_element(nums: list[int]) -> list[int]:
"""Find next greater element for each position."""
n = len(nums)
result = [-1] * n
stack = [] # Stack of indices
for i in range(n):
# Pop elements smaller than current
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result
def next_smaller_element(nums: list[int]) -> list[int]:
"""Find next smaller element for each position."""
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
# Pop elements larger than current
while stack and nums[stack[-1]] > nums[i]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result
def daily_temperatures(temperatures: list[int]) -> list[int]:
"""Days until warmer temperature."""
n = len(temperatures)
result = [0] * n
stack = [] # Stack of indices
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
idx = stack.pop()
result[idx] = i - idx # Days difference
stack.append(i)
return result
def largest_rectangle_histogram(heights: list[int]) -> int:
"""Largest rectangle area in histogram."""
stack = [] # Stack of (index, height)
max_area = 0
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
idx, height = stack.pop()
max_area = max(max_area, height * (i - idx))
start = idx # This index can extend back
stack.append((start, h))
# Process remaining in stack
for idx, height in stack:
max_area = max(max_area, height * (len(heights) - idx))
return max_area
def stock_span(prices: list[int]) -> list[int]:
"""Days since last higher price (inclusive of today)."""
n = len(prices)
result = [0] * n
stack = [] # Stack of indices
for i in range(n):
while stack and prices[stack[-1]] <= prices[i]:
stack.pop()
# Span = distance to previous higher (or from start)
result[i] = i - stack[-1] if stack else i + 1
stack.append(i)
return resultLook for these keywords and patterns in problem descriptions:
Using < when you should use > (or vice versa) results in the wrong
type of monotonic stack.
Fix:
Remember: "next greater" needs decreasing stack, so pop when nums[top] < current.
"Next smaller" needs increasing stack, so pop when nums[top] > current.
Storing just values makes it impossible to calculate distances (like "how many days until...").
Fix:
Store indices in the stack. You can always access nums[stack[-1]] for
the value when needed.
Find the first element to the right that is greater than current. Decreasing monotonic stack.
Examples: Next Greater Element I/II, Daily Temperatures
Find the first element to the right that is smaller than current. Increasing monotonic stack.
Examples: Next Smaller Element
Query the stack before pushing to find the previous greater/smaller. The top of stack is the answer.
Examples: Stock Span, Buildings With Ocean View
Use increasing stack. When popping, calculate area using popped height and width from popped index to current index.
Examples: Largest Rectangle in Histogram, Maximal Rectangle
Can use monotonic stack to track left boundaries, calculating trapped water when finding right boundary. (Alternative: two-pointer approach)
Examples: Trapping Rain Water
Start here to build foundational understanding.
Master the pattern with these representative problems.
Test your mastery with complex variations.
Explore similar techniques:
Use two pointers to traverse data from different positions, often moving toward or away from each other. This technique transforms O(n²) brute force into O(n) by eliminating redundant comparisons.
Maintain a window of elements that slides through the data, tracking a constraint or computing aggregates. This transforms O(n*k) brute force into O(n) by incrementally updating the window instead of recalculating from scratch.
Elements left in the stack after processing all input have no "next greater/smaller" in the array.
Fix:
After the main loop, process remaining elements. For histogram problems, their rectangle extends to the end. For "next greater," their answer is -1.
Forgetting whether to include the current element in span calculations gives wrong results.
Fix:
For span problems, if stack is empty, span = i + 1 (from beginning). If stack has elements, span = i - stack[-1] (not +1 because previous greater is exclusive).