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.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide