Monotonic Stack Patterns: Complete Interview Guide
Monotonic stacks solve a specific family of problems related to “nearest greater/smaller element” queries in O(n) time. Once you recognize the pattern, these problems become straightforward. Tested frequently at Google, Meta, Amazon, and Microsoft.
The Core Idea
A monotonic stack maintains elements in a strictly increasing or decreasing order. When a new element violates this property, we pop until the invariant is restored. The popped elements have found their “answer” — the new element is the nearest element that breaks the monotonic order.
def next_greater_element(nums: list[int]) -> list[int]:
"""
For each element, find the next greater element to the right.
Returns -1 if no greater element exists.
Monotonic decreasing stack: maintain stack of indices
where values are decreasing from bottom to top.
When we see a greater element, it's the answer for all popped elements.
Time: O(n) — each element pushed and popped at most once
Space: O(n)
"""
n = len(nums)
result = [-1] * n
stack = [] # stack of indices, values are decreasing
for i in range(n):
# Current element is greater than stack top — pop and record answer
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is the next greater for nums[idx]
stack.append(i)
# Remaining elements in stack have no next greater element (result stays -1)
return result
# Example:
# nums = [2, 1, 2, 4, 3]
# result = [4, 2, 4, -1, -1]
Pattern Variants
Variant 1: Next Smaller Element
def next_smaller_element(nums: list[int]) -> list[int]:
"""
Monotonic INCREASING stack (values increase from bottom to top).
When we see a smaller element, it's the next smaller for all popped elements.
"""
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing
for i in range(n):
while stack and nums[i] list[int]:
"""Process right to left, or use a different stack direction"""
n = len(nums)
result = [-1] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result
Variant 2: Circular Array
def next_greater_circular(nums: list[int]) -> list[int]:
"""
LeetCode 503. Next Greater Element II (circular array).
Trick: process array twice (2n iterations) to handle wrap-around.
Use modulo to access elements cyclically.
"""
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n): # traverse twice
while stack and nums[i % n] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n: # only push real indices (not the second pass)
stack.append(i)
return result
Classic Problems
Largest Rectangle in Histogram
def largest_rectangle_histogram(heights: list[int]) -> int:
"""
LeetCode 84. Find largest rectangle in histogram.
Key insight: for each bar as the shortest bar, extend left and right
until hitting a shorter bar. Use monotonic increasing stack to find
left and right boundaries efficiently.
Time: O(n), Space: O(n)
"""
stack = [] # monotonic increasing — indices
max_area = 0
n = len(heights)
for i in range(n + 1):
curr_height = heights[i] if i < n else 0 # sentinel 0 at end
while stack and curr_height int:
"""
LeetCode 85. Maximal Rectangle (matrix of 0s and 1s).
Build histogram row by row, apply largest_rectangle_histogram.
Time: O(m*n), Space: O(n)
"""
if not matrix:
return 0
n = len(matrix[0])
heights = [0] * n
max_area = 0
for row in matrix:
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
max_area = max(max_area, largest_rectangle_histogram(heights))
return max_area
Trapping Rain Water
def trap_rain_water(height: list[int]) -> int:
"""
LeetCode 42. Trapping Rain Water.
Monotonic stack approach: when we find a bar taller than stack top,
water is trapped between the new bar and the bar below stack top.
Time: O(n), Space: O(n)
"""
stack = [] # monotonic decreasing (indices)
water = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
bottom = stack.pop() # the "floor" of the water pocket
if not stack:
break
left_wall = stack[-1]
right_wall = i
width = right_wall - left_wall - 1
bounded_height = min(height[left_wall], height[right_wall]) - height[bottom]
water += width * bounded_height
stack.append(i)
return water
# Alternative: Two-pointer O(1) space
def trap_two_pointer(height: list[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < 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 water
Daily Temperatures
def daily_temperatures(temperatures: list[int]) -> list[int]:
"""
LeetCode 739. Days until warmer temperature.
Classic next-greater-element: result[i] = j - i where j is
the next index with a higher temperature.
Time: O(n), Space: O(n)
"""
n = len(temperatures)
result = [0] * n
stack = [] # monotonic decreasing stack of indices
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_idx = stack.pop()
result[prev_idx] = i - prev_idx # days to wait
stack.append(i)
return result # remaining stack elements have result = 0 (never warmer)
Remove K Digits to Minimize Number
def remove_k_digits(num: str, k: int) -> str:
"""
LeetCode 402. Remove k digits to make smallest possible number.
Greedy + monotonic increasing stack: when current digit is smaller
than stack top, pop stack top (remove it) and decrement k.
Time: O(n), Space: O(n)
"""
stack = [] # monotonic increasing
for digit in num:
while k and stack and digit 0, remove from end (stack is already increasing)
result = stack[:-k] if k else stack
# Remove leading zeros, return '0' if empty
return ''.join(result).lstrip('0') or '0'
def largest_number_after_k_removals(num: str, k: int) -> str:
"""Remove k digits to maximize the number — monotonic DECREASING stack"""
stack = []
for digit in num:
while k and stack and digit > stack[-1]:
stack.pop()
k -= 1
stack.append(digit)
result = stack[:-k] if k else stack
return ''.join(result).lstrip('0') or '0'
Sum of Subarray Minimums
def sum_subarray_minimums(arr: list[int]) -> int:
"""
LeetCode 907. For each subarray, find minimum; return total sum.
Key insight: for each element arr[i], count subarrays where it's the minimum.
= (i - left_boundary) * (right_boundary - i)
where left_boundary = previous smaller element index
and right_boundary = next smaller or equal element index
Use TWO monotonic stacks (or combine into one pass).
Time: O(n), Space: O(n)
"""
MOD = 10**9 + 7
n = len(arr)
# Previous smaller element (strict: use < for left, = arr[i]:
stack.pop()
left[i] = i - stack[-1] if stack else i + 1
stack.append(i)
# Next smaller or equal element
right = [0] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
right[i] = stack[-1] - i if stack else n - i
stack.append(i)
return sum(arr[i] * left[i] * right[i] for i in range(n)) % MOD
Problem Recognition Guide
| Signal | Pattern | Stack type |
|---|---|---|
| “Next greater/smaller element” | Monotonic stack | Decreasing / Increasing |
| “Days until…” (time series) | Monotonic stack | Decreasing |
| “Largest rectangle…” | Mono stack + histogram | Increasing |
| “Trapped water” | Mono stack or two-pointer | Decreasing |
| “Remove digits to min/max” | Greedy + mono stack | Increasing / Decreasing |
| “Contribution of each element as min/max” | Mono stack (left+right boundaries) | Both |
Template
def monotonic_stack_template(arr):
"""
Next Greater Element template — adapt for your problem.
"""
n = len(arr)
result = [-1] * n
stack = [] # monotonic decreasing (for next greater)
# monotonic increasing (for next smaller)
for i in range(n):
while stack and arr[i] > arr[stack[-1]]: # > for next greater; < for next smaller
idx = stack.pop()
result[idx] = arr[i] # or i - idx for distance
stack.append(i)
return result