Monotonic stack
hardThe nested while loop looks quadratic, but each index is pushed once and popped at most once - so the whole thing is O(n). Recognising this shape solves half a dozen classic problems at once.
O(n)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How monotonic stack works
Next greater element asks, for each value, for the first larger value to its right. Brute force scans rightward from every index - O(n²). The monotonic stack answers all n queries in one pass by keeping a stack of indices whose values run strictly decreasing from bottom to top.
The stack means one thing: still waiting for an answer. An index sits there precisely while nothing larger has appeared to its right. When a[i] arrives, every stacked index holding a smaller value has just found its next greater element - pop each one, record a[i] as its answer, then push i to wait its own turn.
The nested while loop looks quadratic, but each index is pushed exactly once and popped at most once - 2n stack operations total, so the whole run is O(n). Recognising this shape solves daily temperatures, largest rectangle in a histogram, trapping rain water and stock span with one comparison swapped.
Step by step
- Input 4, 8, 5, 2, 25, 7, 1, 9. Push index 0 - the 4 waits for something larger.
- At 8: the stacked 4 is smaller, so pop it and record result[0] = 8. Push index 1.
- 5 and 2 beat nothing, so each just pushes. The stack's values now read 8, 5, 2 - decreasing, as always.
- At 25: pop 2, then 5, then 8 - three answers recorded in one sweep. Push index 4.
- 7 and 1 stack up under 25. Then 9 arrives: pop 1 and 7, both answered by 9, but 25 stays put.
- End of input. The indices holding 25 and 9 never met a larger value, so their results stay -1. Total pushes and pops: 14 for 8 elements.
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(n) |
Every index enters and leaves the stack at most once: 2n operations total.
Reference implementation
Python
def next_greater(a):
"""For each element, the first larger value to its right."""
n = len(a)
result = [-1] * n
stack = [] # indices, values decreasing
for i, x in enumerate(a):
while stack and a[stack[-1]] < x:
result[stack.pop()] = x
stack.append(i)
return resultJavaScript
function nextGreater(a) {
const result = new Array(a.length).fill(-1);
const stack = []; // indices, values decreasing
for (let i = 0; i < a.length; i++) {
while (stack.length && a[stack.at(-1)] < a[i]) {
result[stack.pop()] = a[i];
}
stack.push(i);
}
return result;
}Worth noticing
Every index is pushed once and popped once
The inner while loop looks like it could make this quadratic, but each index enters the stack exactly once and leaves at most once. Total work is 2n - so the whole thing is O(n) despite the nested loop.
The stack holds 'still waiting for an answer'
An index sits on the stack precisely while no larger value has appeared to its right. The moment one does, it is popped and answered. Anything left at the end never found one.
One pattern, many problems
Daily temperatures, largest rectangle in a histogram, trapping rain water, stock span, remove-k-digits - all the same monotonic stack with a different comparison. Recognising the shape is worth more than memorising any one solution.
Common pitfalls
- Storing values instead of indices: a popped value tells you what was beaten but not where to write the answer. Push indices, read values through them.
- Getting the comparison backwards: a[stack.top] < a[i] finds the next greater; flip it and you are solving next smaller - a different problem that still runs.
- Ignoring strictness with duplicates: whether equal values pop decides which occurrence receives which answer. Match it to the problem statement.
- Forgetting the leftovers: indices still stacked at the end have no next greater element, and the result must say so explicitly - here, -1.
- Assuming the nested loop means O(n²) and reaching for something fancier - each index enters and leaves at most once, so it is already linear.
Where it is used
- Daily temperatures, LeetCode 739 - days until a warmer day is this exact code.
- Largest rectangle in a histogram, where the stack finds how far each bar extends.
- Trapping rain water and stock span - the same skeleton with a different comparison.
- Remove k digits and similar greedy problems, popping larger digits to build the smallest result.
Frequently asked questions
What is the time complexity of a monotonic stack?
O(n) time and O(n) space. The nested while loop is misleading: every index enters the stack exactly once and leaves at most once, so total stack operations are bounded by 2n. The worst case for space is a fully decreasing input, where all n indices stack up.
How do I recognise a problem that needs a monotonic stack?
The phrase to spot is nearest larger or smaller element in one direction: next warmer day, previous smaller price, how far a bar extends. If every element needs its closest dominating neighbour, the pattern applies - one pass, popping everything the newcomer answers.
Should the stack be increasing or decreasing?
Decreasing values find the next greater element - anything smaller than the newcomer pops. Increasing values find the next smaller. Say out loud what a pop means - this index just met its answer - and the problem statement picks the direction for you.
What happens to elements still on the stack at the end?
They never found an answer - no larger value ever appeared to their right - so they keep the sentinel -1. In this run of 4, 8, 5, 2, 25, 7, 1, 9, that is the 25 and the final 9.