Monotonic Stack Pattern Explained — How, Why, and When to Use It
- A monotonic stack maintains sorted order, discarding elements that can never be useful.
- Each element is pushed and popped at most once — total O(n) time for the entire algorithm.
- Decreasing stack: pop when arr[new] > arr[top] → finds next greater element.
Imagine you're standing in a line at a concert, and everyone wants to know: 'Who's the next taller person behind me?' Instead of every person turning around and scanning the whole crowd (slow!), you use a bouncer who maintains a running list — kicking out anyone shorter as taller people arrive. That bouncer's list is your monotonic stack. It's always sorted, always current, and always answers your question in one pass.
Most developers hit a wall with array problems that demand knowing the 'next greater' or 'previous smaller' element at every index. The naive approach — a nested loop — works on paper but collapses at scale. When you're processing stock prices, rendering bar charts, or evaluating weather forecasts over millions of data points, O(n²) isn't a trade-off; it's a dealbreaker. The monotonic stack pattern is one of those rare tools that turns a quadratic problem into a linear one without any exotic data structure magic — just a regular stack used with discipline.
The core problem it solves is deceptively simple: for each element in an array, find the nearest element to its left or right that is greater or smaller than it. Brute force checks every pair. The monotonic stack makes one observation that changes everything — if you're scanning left-to-right and you encounter an element that 'dominates' the element on top of the stack, the dominated element has found its answer. You process it, pop it, and never look at it again. That amortized O(1) pop-per-element is where the O(n) total time comes from.
By the end of this article you'll be able to implement both monotonically increasing and decreasing stacks from scratch, identify which variant a problem requires, handle tricky edge cases like duplicate values and circular arrays, and explain the amortized time complexity to an interviewer without flinching. You'll also walk away with a mental checklist that maps problem phrasing directly to the right stack orientation — so you stop guessing.
What is Monotonic Stack? — Plain English
A monotonic stack maintains elements in either strictly increasing or strictly decreasing order. When a new element is pushed, any elements on the stack that violate the monotonic property are popped first. The moment an element is popped because of a new incoming element, that defines a relationship — typically 'the next greater element' or 'the next smaller element'.
Monotonic stacks solve in O(n) problems that naively take O(n^2): next greater element, previous smaller element, largest rectangle in histogram, trapped rainwater.
How Monotonic Stack Works — Step by Step
Monotonic decreasing stack (for next greater element): 1. Initialize an empty stack. 2. For each index i from left to right: a. While the stack is non-empty and arr[stack[-1]] < arr[i]: - Pop index j from the stack. - result[j] = arr[i] (arr[i] is the next greater element for arr[j]). b. Push index i onto the stack. 3. For any index remaining in the stack: result[j] = -1 (no greater element).
Monotonic increasing stack (for next smaller element) — same idea but flip the comparison.
Worked Example — Tracing the Algorithm
Find next greater element for [4, 5, 2, 10, 8].
i=0 (4): stack empty. Push 0. stack=[0]. i=1 (5): arr[0]=4 < 5. Pop 0. result[0]=5. Stack empty. Push 1. stack=[1]. i=2 (2): arr[1]=5 >= 2. Push 2. stack=[1,2]. i=3 (10): arr[2]=2 < 10. Pop 2. result[2]=10. arr[1]=5 < 10. Pop 1. result[1]=10. Stack empty. Push 3. stack=[3]. i=4 (8): arr[3]=10 >= 8. Push 4. stack=[3,4]. End: stack has [3,4] remaining. result[3]=-1, result[4]=-1.
Result: [5, 10, 10, -1, -1] Reading: next greater than 4 is 5, next greater than 5 is 10, next greater than 2 is 10, 10 and 8 have no greater element.
Implementation
The implementation maintains a stack of indices (not values). When processing element arr[i], pop all indices j where arr[j] <= arr[i] (for next-greater) and record arr[i] as the answer for position j. Any indices still on the stack at the end have no greater element to their right, so their answer is -1. This single pass runs in O(n) time and O(n) space. The same pattern works for next-smaller, previous-greater, and previous-smaller by flipping the comparison or iterating right-to-left.
def next_greater_element(arr): n = len(arr) result = [-1] * n stack = [] # monotonic decreasing stack (stores indices) for i in range(n): while stack and arr[stack[-1]] < arr[i]: j = stack.pop() result[j] = arr[i] stack.append(i) # remaining indices in stack have no greater element → -1 (default) return result print(next_greater_element([4, 5, 2, 10, 8])) # [5, 10, 10, -1, -1]
| Concept | Use Case | Example |
|---|---|---|
| Monotonic Stack Pattern | Core usage | See code above |
🎯 Key Takeaways
- A monotonic stack maintains sorted order, discarding elements that can never be useful.
- Each element is pushed and popped at most once — total O(n) time for the entire algorithm.
- Decreasing stack: pop when arr[new] > arr[top] → finds next greater element.
- Increasing stack: pop when arr[new] < arr[top] → finds next smaller element.
- Common applications: next greater element, previous smaller element, histogram rectangles, trapped rainwater.
⚠ Common Mistakes to Avoid
Interview Questions on This Topic
- QWhat is a monotonic stack and when should you use one?
- QWalk through the 'next greater element' algorithm with a concrete example.
- QHow does a monotonic stack achieve O(n) when a naive solution is O(n^2)?
Frequently Asked Questions
What makes a stack 'monotonic' and why does that help?
A stack is monotonic if its elements are always in sorted order (increasing or decreasing) from bottom to top. This ensures that when an element is popped because a larger/smaller element arrived, the pop answers the 'next greater/smaller' question directly. Without the monotonic invariant, you'd need to scan the entire array for each element — O(n^2).
What is the classic 'largest rectangle in histogram' and how does the monotonic stack help?
For each bar, the largest rectangle with that bar as the shortest bar extends left to the first shorter bar and right to the first shorter bar. A monotonic increasing stack (of indices in increasing height order) finds both left and right boundaries: when a bar is popped because a shorter bar arrived, we know the right boundary is the current index and the left boundary is the new stack top.
Can a monotonic stack process elements from right to left?
Yes. For 'previous greater element', traverse right to left and use the same logic. The stack stores candidates that might be the previous greater element for future (earlier) indices. Right-to-left traversal is also used for next smaller element in some formulations.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.