Monotonic Stack Core Idea
A monotonic stack maintains elements in a sorted order (increasing or decreasing). As new elements arrive, pop elements that violate the monotonic property before pushing. The popped elements are those for which the new element is the answer. Use when: you need to find the “next greater/smaller element” for each position, or when you’re looking for boundaries of a range (largest rectangle, trapping rain water). O(n) total — each element is pushed and popped at most once.
Pattern 1: Next Greater Element (LC 496, 503)
For each element, find the next element to its right that is greater. Monotonic decreasing stack (stack holds indices of elements in decreasing order of value). For each new element: pop all indices with values <= current. For each popped index: the current element is its next greater element. Push current index.
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
idx = stack.pop()
result[idx] = val
stack.append(i)
return result
# Circular array (LC 503): process 2n indices, mod n
def next_greater_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
result[stack.pop()] = nums[i % n]
if i < n: stack.append(i)
return resultPattern 2: Largest Rectangle in Histogram (LC 84)
For each bar, find how far it can extend left and right (until a shorter bar). Use a monotonic increasing stack: when a bar shorter than the stack top is encountered, pop and compute the rectangle. The popped bar’s width extends from the new stack top + 1 to the current position – 1.
def largest_rectangle(heights):
stack = [-1] # sentinel
max_area = 0
for i, h in enumerate(heights):
while stack[-1] != -1 and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
while stack[-1] != -1:
height = heights[stack.pop()]
width = len(heights) - stack[-1] - 1
max_area = max(max_area, height * width)
return max_areaPattern 3: Stock Span (LC 901) and Daily Temperatures (LC 739)
LC 739 (Daily Temperatures): for each day, find how many days until a warmer temperature. Monotonic decreasing stack of indices. When current temperature > stack top: pop; the answer for the popped index = current_index – popped_index. LC 901 (Online Stock Span): for each price, count consecutive previous days with price = stack top price: pop and accumulate the span. Push (current_price, accumulated_span + 1). These problems follow the same template: pop elements when a “dominant” new element arrives.
Pattern 4: Sum of Subarray Minimums (LC 907)
For each element, find how many subarrays it is the minimum of. Left boundary: distance to the previous smaller element (use monotonic stack scanning left-to-right). Right boundary: distance to the next smaller or equal element (scan right-to-left). Number of subarrays where nums[i] is the minimum = left_dist[i] * right_dist[i]. Contribution = nums[i] * left_dist[i] * right_dist[i]. Sum all contributions. O(n) total. The key insight: instead of iterating over all O(n^2) subarrays, compute each element’s contribution directly by finding its dominance range. This contribution technique also applies to sum of subarray maximums (LC 2104) and largest rectangle area problems.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How do you choose between a monotonic increasing and monotonic decreasing stack?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Monotonic decreasing stack (top has the smallest value): used for “next greater element” problems. When a new element is larger than the top, pop — the new element is the answer for the popped elements. Pop condition: new element > stack top. Monotonic increasing stack (top has the largest value): used for “next smaller element” problems. When a new element is smaller than the top, pop — the new element is the “next smaller” for popped elements. Pop condition: new element < stack top. Mental model: think about what triggers a pop. If you pop when a LARGER element arrives: you get the next GREATER element for each popped item. If you pop when a SMALLER element arrives: you get the next SMALLER element. For the largest rectangle in histogram: you pop when a SHORTER bar arrives (the stack is increasing — taller bars to the right). The popped bar found its right boundary. For the trapping rain water stack approach: pop when a TALLER bar arrives (decreasing stack — water fills the valley between the popped bar and the new taller bar). Choose based on what "dominates" — the condition that ends the dominance of a stack element is the pop condition."
}
},
{
"@type": "Question",
"name": "How does the monotonic stack solve the trapping rain water problem differently from two pointers?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Stack approach: use a monotonic decreasing stack of indices (decreasing values). When a taller bar is encountered (pop condition): a valley exists between the popped element and the current element. The left wall is the new stack top (after the pop). Calculate the trapped water in this valley: width = current_index – stack_top_index – 1. height = min(height[current], height[new_stack_top]) – height[popped]. water += width * height. This approach calculates water layer by layer (horizontal slices). Two-pointer approach: calculates water column by column (vertical slices) — one column's worth of water per iteration. Both are O(n) time and solve the same problem. Two-pointer uses O(1) space; stack uses O(n) space. In interviews: the two-pointer approach is slightly more elegant. The stack approach is easier to generalize to similar problems (like the maximal rectangle in a binary matrix, which extends the histogram problem). Know both; state your preference."
}
},
{
"@type": "Question",
"name": "How do you extend the largest rectangle in histogram to find the maximal rectangle in a binary matrix (LC 85)?",
"acceptedAnswer": {
"@type": "Answer",
"text": "For each row of the matrix, compute the height of consecutive 1s ending at that row (the histogram heights). Then run the largest rectangle in histogram algorithm on those heights. Heights computation: heights[j] = heights[j] + 1 if matrix[row][j] == '1' else 0. This counts the number of consecutive 1s from the top to the current row in each column. For each row's histogram: apply the O(n) monotonic stack algorithm to find the largest rectangle. The overall answer is the max rectangle area across all row histograms. Total time: O(m * n) where m = rows, n = columns. Space: O(n) for the heights array and stack. Example: for a 4×4 matrix with a 3×3 block of 1s, the maximum area = 9. The algorithm discovers this when processing row 3 (heights = [3,3,3,…] for the 3 middle columns) — largest rectangle = 3 * 3 = 9. This extension works because each row's histogram captures all rectangles that have their bottom edge in that row."
}
},
{
"@type": "Question",
"name": "What is the asteroid collision problem (LC 735) and how does it use a stack?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Asteroids move right (+) or left (-). When two asteroids meet (one moving right, one moving left), the smaller one explodes. Equal sizes both explode. Find the state after all collisions. Stack-based simulation: iterate through asteroids. If the current asteroid is positive (moving right): push to stack (no collision yet, it moves away from any right-moving asteroid). If negative (moving left): it may collide with the top of the stack (if stack top is positive = right-moving). While the stack is non-empty and the top is positive: compare absolute values. If current has greater absolute value: the stack top explodes (pop), current continues. If equal: both explode (pop stack top, skip current). If stack top has greater absolute value: current explodes (break). If the stack is empty or the top is negative (both moving left, no collision): push current. The stack maintains surviving right-moving asteroids. Left-moving asteroids resolve against them. Final stack = surviving asteroids. O(n) time — each asteroid is pushed and popped at most once."
}
},
{
"@type": "Question",
"name": "How do you find the number of visible people in a queue (LC 1944) using a monotonic stack?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Person i can see person j if all persons between them are shorter than both. Find for each person how many people they can see looking right. Monotonic decreasing stack (like next greater element, but count all popped elements, not just the first). Process right to left: for each person at index i, pop all people from the stack shorter than heights[i] — person i can see all of them. The count of popped people = number of people visible at or shorter than i. If the stack is still non-empty after popping (a taller person remains): person i can also see that taller person (add 1). So: answer[i] = popped_count + (1 if stack non-empty else 0). Key insight: a short person is "blocked" by the next taller person — they can only see people up to and including the next taller one. The stack maintains the set of people that might still block future people (decreasing heights). Popped people were shorter than the current person and are now fully occluded by them for anyone looking from the left."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide