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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is a monotonic stack and what types of problems does it solve?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “A monotonic stack is a stack that maintains its elements in monotonically increasing or decreasing order by popping elements that violate the property when a new element is pushed. It solves “nearest neighbor” problems efficiently in O(n): finding the next greater element, next smaller element, previous greater/smaller element for each position in an array. The key insight: when an element is popped because a new element violates the monotonic property, the new element is the “next greater/smaller” answer for the popped element. Since each element is pushed and popped at most once, the total work across all iterations is O(n). Common problems: Next Greater Element (decreasing stack u2014 pop when current > top), Largest Rectangle in Histogram (increasing stack u2014 pop when current < top), Trapping Rain Water (decreasing stack), Daily Temperatures (decreasing stack u2014 result is distance), Remove K Digits (increasing stack u2014 pop larger digits to minimize number). Identifying the pattern: "for each element, find the first element to its left/right that is greater/smaller" u2192 monotonic stack."
}
},
{
"@type": "Question",
"name": "How does the Largest Rectangle in Histogram algorithm work?",
"acceptedAnswer": {
"@type": "Answer",
"text": "For each bar at index i, the largest rectangle extending over bar i has height = heights[i] and extends left to the nearest shorter bar and right to the nearest shorter bar. The monotonic increasing stack approach computes this in O(n). Maintain a stack of bar indices in increasing order of height. When heights[i] = heights[stack.top()]. Then push i. Add sentinel bars of height 0 at both ends: the left sentinel gives all pops a valid left boundary (width calculation: i – (-1) – 1 = i), and the right sentinel forces all remaining bars to be popped at the end. Time O(n), space O(n).”
}
},
{
“@type”: “Question”,
“name”: “How do you solve Trapping Rain Water using a monotonic stack?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Water is trapped in valleys u2014 between a lower bar and taller bars on both sides. The monotonic decreasing stack approach processes bars left to right, tracking potential left walls. When heights[i] > heights[stack.top()], the stack top is a valley bottom that can trap water. Pop the bottom (call its index mid). The left wall is the new stack top (if it exists); the right wall is the current bar i. Water trapped = width u00d7 (min(left_wall_height, right_wall_height) – bottom_height). Width = i – left_wall_index – 1. Accumulate water for each popped valley bottom. In code: while stack and heights[i] > heights[stack[-1]]: bottom_idx = stack.pop(); if not stack: break; width = i – stack[-1] – 1; bounded_h = min(heights[i], heights[stack[-1]]) – heights[bottom_idx]; water += width * bounded_h. Then stack.append(i). The two-pointer approach is simpler (O(1) space): track left_max and right_max; water at position i = max(0, min(left_max, right_max) – heights[i]). Advance from whichever side has the smaller max u2014 the smaller side’s water level is determined by its own max, not the other side’s.”
}
}
]
}