What Is a Monotonic Stack?
A monotonic stack is a stack that maintains its elements in either monotonically increasing or monotonically decreasing order. When a new element violates the monotonic property, elements are popped until the property is restored. This makes the stack useful for efficiently finding the “next greater element”, “previous smaller element”, or similar “nearest neighbor” queries in O(n) time — problems that would otherwise require O(n²) brute force.
Next Greater Element (Monotonic Decreasing Stack)
For each element, find the first element to its right that is greater. Maintain a stack of elements (or indices) in decreasing order. When processing nums[i]: while the stack is not empty and nums[i] > stack.top(), pop the top — nums[i] is the “next greater” for that popped element. Push nums[i] onto the stack. Elements remaining in the stack at the end have no next greater element (-1).
def nextGreaterElement(nums):
result = [-1] * len(nums)
stack = [] # stores indices
for i in range(len(nums)):
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result
Each element is pushed and popped at most once → O(n) time. The key insight: when we pop an element, we have found its answer.
Next Greater Element II (Circular Array)
For a circular array, iterate twice (indices 0 to 2n-1) using modulo indexing (i % n). On the second pass, only push indices from the first pass (i < n already in stack) — don't push new indices on the second pass.
Largest Rectangle in Histogram (LC 84)
Classic monotonic stack problem. For each bar, the maximum rectangle extending over that bar has height = bar’s height and width = the range between the nearest shorter bar on the left and nearest shorter bar on the right.
def largestRectangleArea(heights):
heights = [0] + heights + [0] # sentinel bars at both ends
stack = [0] # indices
max_area = 0
for i in range(1, len(heights)):
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1 # left boundary = new stack top + 1
max_area = max(max_area, h * w)
stack.append(i)
return max_area
The sentinel 0 at both ends ensures the stack always has a base element and all bars are popped before termination. When popping index j with height h, the width is from (new stack top + 1) to (current i – 1) = i – stack[-1] – 1.
Maximal Rectangle (LC 85)
Given a binary matrix, find the largest rectangle containing only 1s. Build a histogram: for each row, compute the “height” of consecutive 1s ending at that row (height[j] += 1 if matrix[i][j] == ‘1’, else height[j] = 0). Apply the largest rectangle in histogram algorithm to each row’s histogram. Time O(m×n), space O(n).
Trapping Rain Water (LC 42)
Find total water trapped between bars. Monotonic stack approach: maintain a decreasing stack. When we encounter a bar higher than the stack top, water can be trapped:
def trap(height):
stack = []
water = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
bottom = stack.pop()
if not stack: break
width = i - stack[-1] - 1
bounded_height = min(height[i], height[stack[-1]]) - height[bottom]
water += width * bounded_height
stack.append(i)
return water
Alternative: two-pointer approach tracks left_max and right_max and is O(1) space. The monotonic stack approach is more general and handles the “how much water above each cell” interpretation naturally.
Daily Temperatures (LC 739)
For each day, find the number of days until a warmer temperature. This is Next Greater Element with the result being the distance (i – popped_index) rather than the value. Monotonic decreasing stack of indices. O(n) time.
Stock Span Problem
For each day, find how many consecutive days (including today) the stock price was ≤ today’s price. Monotonic decreasing stack of (price, span) pairs. When pushing a new price, pop all smaller prices and accumulate their spans. Push (new_price, accumulated_span + 1). O(n) time.
def stockSpan(prices):
stack = [] # (price, span)
result = []
for p in prices:
span = 1
while stack and stack[-1][0] <= p:
span += stack.pop()[1]
stack.append((p, span))
result.append(span)
return result
Remove K Digits (LC 402)
Remove k digits to make the smallest possible number. Monotonic increasing stack: for each digit, while the stack is not empty, the top digit is larger than the current digit, and k > 0: pop the top (this is a digit we remove). Push the current digit. After processing, if k > 0, remove from the end. This greedy strategy always removes larger digits from the front, minimizing the resulting number.
Pattern Recognition Guide
Use a monotonic decreasing stack (stack maintained largest-to-smallest from bottom to top) for: next greater element, largest rectangle, trapping rain water. Pop when current element is LARGER than top.
Use a monotonic increasing stack (stack maintained smallest-to-largest) for: next smaller element, remove k digits to minimize. Pop when current element is SMALLER than top.
The firing condition is the key: “pop when the current element would violate the monotonic property.” Whatever gets popped has the current element as its answer.
Companies That Ask This
Asked at: Airbnb Interview Guide