What is the Monotonic Stack Technique?
Learn the monotonic stack technique, how it solves nearest-comparison problems in O(n), and how to answer this interview question.
Expected Interview Answer
A monotonic stack is a stack that is kept either strictly increasing or strictly decreasing from bottom to top by popping any element that would violate that order before pushing the new one, and it is the general technique behind next-greater-element, largest-rectangle-in-histogram, and daily-temperature style problems, running in amortized O(n) time.
The core idea is that before pushing a new element, you pop everything on top that would break the required order, and each popped element is exactly the answer to a "nearest boundary" question for the element being popped — a decreasing stack answers "who is my next greater element" while an increasing stack answers "who is my next smaller element," and scanning from the other direction answers the "previous" version of the same question. Because each element is pushed exactly once and popped at most once across the whole scan, the total work is O(n) even though the popping happens inside a while loop that looks like it could be quadratic. The pattern generalizes powerfully: largest rectangle in histogram uses an increasing stack of bar heights to find, for each bar, how far left and right it can expand before hitting a shorter bar, and trapping rain water can be solved with a decreasing stack tracking potential water-holding walls. Recognizing “for each element, find the nearest element to the left/right satisfying some comparison” is the signal to reach for a monotonic stack instead of nested loops.
- Turns O(n^2) nearest-comparison problems into O(n)
- Each element pushed once and popped at most once (amortized linear)
- One core pattern powers next-greater, histogram, and rain-water problems
- Works in either direction (left-to-right or right-to-left) and either monotonic order
AI Mentor Explanation
A tournament organizer stacking teams by strength keeps the line strictly ordered — say, strongest at the bottom, weakest at the top — by knocking out any team from the top of the line that a newly arriving stronger team would outrank before that new team joins. Each knocked-out team's elimination is itself the answer to "who was the first stronger team to come along after them", so the popping isn't wasted work, it's the actual result. Because every team enters the line once and gets knocked out at most once across the whole event, tallying every team's elimination is a single linear pass, not a full round-robin comparison. This same discipline of maintaining a strictly ordered line while popping violators is the monotonic stack technique underneath many nearest-comparison problems.
Step-by-Step Explanation
Step 1
Decide the monotonic order
Increasing stack answers "next/previous smaller element" questions; decreasing stack answers "next/previous greater element" questions.
Step 2
Scan and pop violators
Before pushing the current element, pop everything on top that would break the required strict order.
Step 3
Record the answer at pop time
Each popped element's answer is the element currently being processed — that comparison is the actual result, not a side effect.
Step 4
Push and continue
Push the current element after resolving all violators, then move to the next element; anything left on the stack at the end has no answer.
What Interviewer Expects
- Explain the "pop until order restored, then push" mechanic precisely
- Connect the technique to at least two concrete problems (next greater element, histogram, trapping rain water)
- Justify amortized O(n) via the push-once-pop-at-most-once argument
- Know when to scan left-to-right vs right-to-left based on "next" vs "previous" wording
Common Mistakes
- Treating the monotonic stack as only solving next-greater-element rather than recognizing it as a general pattern
- Storing values instead of indices, losing the ability to compute distances or write results at the right position
- Popping strictly vs non-strictly incorrectly, causing wrong results on duplicate values
- Not recognizing "for each element, find the nearest X to the left/right" as the trigger phrase for this pattern
Best Answer (HR Friendly)
“A monotonic stack is a stack I keep strictly increasing or strictly decreasing by popping anything that breaks that order right before I push a new item. The trick is that each pop isn't wasted — it's actually answering a question like "who is the next bigger or smaller item" for whatever just got popped. Because every item only goes on and comes off the stack once, this turns a problem that looks like it needs nested loops into a single linear pass.”
Code Example
def next_greater(nums):
n = len(nums)
result = [-1] * n
stack = [] # decreasing stack of indices
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
resolved_idx = stack.pop()
result[resolved_idx] = val # pop IS the answer
stack.append(i)
return result
# Same skeleton, increasing stack, solves "next smaller element"
def next_smaller(nums):
n = len(nums)
result = [-1] * n
stack = [] # increasing stack of indices
for i, val in enumerate(nums):
while stack and nums[stack[-1]] > val:
resolved_idx = stack.pop()
result[resolved_idx] = val
stack.append(i)
return resultFollow-up Questions
- How would you use a monotonic stack to solve the largest rectangle in histogram problem?
- How does the monotonic stack pattern apply to the trapping rain water problem?
- How would you find the previous smaller element instead of the next one?
- When would a monotonic deque be needed instead of a plain monotonic stack (e.g. sliding window maximum)?
MCQ Practice
1. What is the defining property of a monotonic stack?
A monotonic stack enforces a strict increasing or decreasing order by popping violators before every push.
2. Why is popping in a monotonic stack considered useful work rather than overhead?
The element that triggers a pop is exactly the nearest-greater or nearest-smaller answer for the popped element, making each pop productive.
3. Which class of problems is the monotonic stack technique best suited for?
The monotonic stack pattern directly answers "nearest element satisfying a comparison" queries for every element in O(n).
Flash Cards
What does "monotonic" mean for a monotonic stack? — Its elements stay strictly increasing or strictly decreasing from bottom to top at all times.
When an element is popped, what does that represent? — The popped element has found its nearest greater (or smaller) neighbor — the element that triggered the pop.
What is the amortized time complexity of a monotonic stack scan? — O(n), since each element is pushed once and popped at most once.
Name two classic problems solved with a monotonic stack. — Next greater element and largest rectangle in histogram (also trapping rain water).