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
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is a monotonic stack and what problems does it solve?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A monotonic stack is a stack that maintains elements in strictly increasing or decreasing order from bottom to top. When a new element violates this invariant, elements are popped until the order is restored. The key insight: when an element is popped, the new element is the ‘answer’ for the popped element — it’s the next element that breaks the monotonic property. Use monotonic stacks for: next greater/smaller element problems, largest rectangle in histogram, trapping rain water, daily temperatures, and any problem asking ‘for each element, find the nearest element satisfying some condition.'”}},{“@type”:”Question”,”name”:”When do you use a monotonic increasing vs decreasing stack?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Monotonic DECREASING stack (values decrease from bottom to top) is used when you want to find the NEXT GREATER element. When you push a new element that’s larger than the top, the top has found its next greater element. Monotonic INCREASING stack (values increase from bottom to top) is used when you want to find the NEXT SMALLER element. When you push a new element that’s smaller than the top, the top has found its next smaller element. Memory trick: ‘decreasing stack finds greater elements’ — the stack is looking downward (smaller elements stay), so the first bigger thing that comes along breaks the pattern.”}},{“@type”:”Question”,”name”:”How do you solve the Largest Rectangle in Histogram problem?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use a monotonic increasing stack (indices). Iterate through bars: when current bar is shorter than stack top, the stack top has found its right boundary (current bar) and left boundary (new stack top after pop). Area = height[popped] * (right_boundary – left_boundary – 1). Append a sentinel bar of height 0 at the end to force all remaining elements to be popped and computed. Time complexity O(n) — each bar is pushed and popped exactly once. This pattern extends to Maximal Rectangle (LeetCode 85): build a histogram row by row and apply this algorithm to each row’s histogram.”}},{“@type”:”Question”,”name”:”How do you handle circular array problems with monotonic stack?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For circular arrays (like Next Greater Element II, LeetCode 503), process the array twice: iterate from i=0 to 2n-1, using i%n to access elements cyclically. On the first pass (i < n), push indices to the stack normally. On the second pass (i >= n), only pop from the stack (don’t push new indices). This simulates ‘wrapping around’ — elements that had no next greater in a linear scan get a chance to find one in the second pass. The duplicate processing handles the circular nature without actually duplicating the array.”}},{“@type”:”Question”,”name”:”What is the time complexity of monotonic stack algorithms?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Monotonic stack algorithms are O(n) time despite the while loop inside the for loop. The key insight: each element is pushed onto the stack exactly once and popped at most once. Total pushes = n, total pops <= n, so total operations = O(2n) = O(n). This is the amortized analysis — even though individual iterations might pop multiple elements, the total across all iterations is bounded by n. Space complexity is O(n) for the stack. This O(n) solution replaces the naive O(n²) approach of checking each element against all others.”}}]}