Monotonic Stack: The Pattern Behind "Next Greater Element" Questions
If a question asks for the next greater, previous smaller, or "how many days until a warmer temperature", a monotonic stack usually turns an O(n²) scan into O(n).
Core idea
Keep a stack of indices whose values are in sorted order (decreasing for "next greater"). When a new value breaks the order, it is the answer for every index you pop.
def daily_temperatures(temps): # LeetCode 739
ans = [0] * len(temps)
stack = [] # indices, temps decreasing
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
ans[j] = i - j
stack.append(i)
return ans
Each index is pushed and popped at most once, so the loop is O(n) even with the inner while.
Choosing the direction
| Question asks for | Stack keeps values | Pop when new value is |
|---|---|---|
| Next greater | decreasing | greater |
| Next smaller | increasing | smaller |
| Previous greater | decreasing | greater or equal (answer = new top) |
Harder problems that use it
- Largest Rectangle in Histogram (84): increasing stack; when a bar is popped, its width runs from the new stack top to the current index.
- Trapping Rain Water (42): popping a lower bar between two taller ones gives the water above it.
- Sum of Subarray Minimums (907): previous-smaller and next-smaller distances give how many subarrays each element is the minimum of. Handle duplicates with
<on one side and<=on the other.
How to explain it in the interview
Say why it is linear: "Every element enters and leaves the stack once." Then trace a 5-element example on the whiteboard; interviewers care more about the invariant than the code.
Disclosure: I work on Linkjob AI's coding interview assistant. This write-up is general practice material.