Next Greater Element
Push elements onto a decreasing stack. When a larger element arrives, pop all smaller elements — for each popped element, the larger element is their 'next greater'. Everything gets pushed and popped exactly once → O(n).
How It Works
The next-greater-element problem asks, for each item, where the first larger value to its right is. A monotonic stack answers this in one pass: walk the array pushing indices, and whenever the current value exceeds the value at the top of the stack, pop — the current element is the answer for every popped index. The stack always holds indices whose answers are still unknown, in decreasing value order.
Each index is pushed and popped at most once, so the total work is O(n) despite the nested-looking while loop — a large win over the O(n²) brute force that rescans rightward for every element.
Step-by-Step Visualization
Code
static int[] dailyTemperatures(int[] temps) {
int[] result = new int[temps.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < temps.length; i++) {
while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
int j = stack.pop();
result[j] = i - j;
}
stack.push(i);
}
return result;
}
// Example: [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]Tips & Gotchas
Practice Problems
- 1Next Greater Element I
- 2Next Greater Element II
- 3Daily Temperatures
About the Monotonic Stack Pattern
Keep the stack in sorted order (always increasing or always decreasing). When a new element would break the order, pop elements until the order is restored. Each popped element just found its 'answer' (the element that caused the pop).
Monotonic stacks are the power tool here. If you need 'next greater/smaller element' or 'span' queries, a monotonic stack gives O(n) instead of O(n²).
Common Stack Interview Problems
- Valid Parentheses
- Next Greater Element
- Largest Rectangle in Histogram
- Trapping Rain Water
- Daily Temperatures
- Decode String
Frequently Asked Questions
Why is the monotonic stack O(n) when it contains a loop inside a loop?
Amortized analysis: every index enters the stack once and leaves at most once, so all pop operations combined cost O(n). The inner while loop's total iterations across the whole scan are bounded by the number of pushes.
Should the stack store values or indices?
Store indices. They let you compute distances (as in Daily Temperatures) and still give you values via the array lookup, whereas storing raw values loses position information.
How do I handle a circular array like Next Greater Element II?
Iterate the array twice (indices 0 to 2n−1) and use i mod n to read values. Only push indices during the first pass; the second pass exists purely to resolve elements whose next greater value wraps around.