Find the next greater or smaller element in O(n) using a stack that maintains sorted order.
A monotonic stack is a stack where the elements are always in increasing (or decreasing) order from bottom to top. When a new element would violate this order, we pop elements until the order is restored. The magic: each pop reveals the answer for the popped element.
We scan the array left to right. The stack holds "unresolved" elements that are still waiting for their answer. When a new element causes pops, it becomes the answer for every popped element.
Why does this work? The stack holds elements that have not yet found their "next greater." The moment a larger element appears, it is by definition the next greater element for everything smaller sitting on top of the stack. We pop them because they are now resolved.
Look for these recognition signals in the problem statement. If you spot one, a monotonic stack is very likely the intended approach.
"Next greater element" or "next smaller element"
"Previous greater/smaller element"
"Stock span" or "daily temperatures"
"Histogram" or "trapping rain water"
The key clue: You need to find, for each element, the nearest element that is larger or smaller than it. A brute-force nested loop would be O(n²). The monotonic stack solves it in O(n) by cleverly processing elements in order and immediately resolving relationships as they appear.
The stack holds elements in decreasing order (from bottom to top). When a new element is larger than the top, we pop. Each popped element's "next greater" is the new element. This is the most common variant.
Find the next greater element for each position. Result: [4, 2, 4, -1, -1]
The stack holds elements in increasing order (from bottom to top). When a new element is smaller than the top, we pop. Each popped element's "next smaller" is the new element. This is the mirror image of Variant 1.
Find the next smaller element for each position. Result: [-1, 4, 4, -1]
Choosing the variant: If you want the next greater element, use a decreasing stack (pop when new > top). If you want the next smaller element, use an increasing stack (pop when new < top). The invariant always matches what you are searching for.
Here is the annotated Java template for the "next greater element" variant. Adapt the comparison operator for "next smaller."
// Next Greater Element for each index int[] nextGreater(int[] nums) { int n = nums.length; int[] result = new int[n]; Arrays.fill(result, -1); // default: no answer Deque<Integer> stack = new ArrayDeque<>(); // stores INDICES for (int i = 0; i < n; i++) { // Pop all elements smaller than current while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) { result[stack.pop()] = nums[i]; // current is the answer } stack.push(i); // push current index } // Elements remaining on stack have no next greater (-1) return result; }
// Next Smaller Element: change < to > while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) { result[stack.pop()] = nums[i]; }
Store indices, not values. The stack stores indices rather than values. This is critical because the result array is indexed by position. When we pop an index from the stack, we know exactly which position in the result array to fill.
Let us trace through a larger example step by step, showing the stack and result array side by side at every stage.
Finding next greater element for each position.
| STEP | ACTION | STACK | RESULT |
|---|---|---|---|
| i=0 (4) | Push 0 | [0:4] | [-1, -1, -1, -1, -1] |
| i=1 (5) | Pop 0res[0]=5, push 1 | [1:5] | 5, -1, -1, -1, -1 |
| i=2 (2) | 2 ≤ 5, push 2 | [1:5, 2:2] | 5, -1, -1, -1, -1 |
| i=3 (10) | Pop 2res[2]=10 Pop 1res[1]=10, push 3 |
[3:10] | 5, 10, 10, -1, -1 |
| i=4 (8) | 8 ≤ 10, push 4 | [3:10, 4:8] | 5, 10, 10, -1, -1 |
Notice the pattern: Each element is pushed exactly once and popped at most once. That means the total number of push + pop operations across the entire loop is at most 2n, giving us O(n) total time, not O(n²).
These are the classic LeetCode problems that use the monotonic stack pattern, listed in rough order of difficulty.
Practice tip: Start with #496 (direct application of the template) and #739 (store index differences instead of values). Once comfortable, tackle #84 which uses a monotonic stack in a more creative way: finding the nearest smaller bar on each side to compute rectangle widths.
Enter an array and step through the monotonic stack algorithm. Watch the stack grow and shrink, and see the result array fill in as pops resolve elements.
Even though there is a while loop inside the for loop, the total work is bounded. Each element is pushed exactly once and popped at most once. Over the entire algorithm, there are at most n pushes and at most n pops. Total operations: O(n + n) = O(n).
Space: The stack can hold at most n elements (when the array is already sorted in the desired order), plus the result array of size n. Total: O(n).
Amortized analysis: The inner while loop might run multiple times for a single iteration of i, but those pops can never happen again for those elements. Across all iterations of i, the total number of pops is bounded by n. This amortized cost is what makes the algorithm linear despite the nested loop.
Push once, pop once = O(n). Each element is pushed onto the stack exactly once and popped at most once. This is the fundamental reason the algorithm runs in linear time, not quadratic time, despite the nested loop.
Decreasing stack for "next greater," increasing for "next smaller." The stack's order invariant directly corresponds to what you are searching for. Flip the comparison operator to switch between variants.
Store indices, not values. The stack holds indices so you can fill the result array at the correct position. You can always look up the value via the original array.
Unresolved elements stay on the stack. After processing all elements, anything left on the stack never found an answer. Their result is -1 (or whatever the default is).
Extends to circular arrays and histograms. For circular arrays (like #503), process the array twice by iterating with i % n. For histogram problems, the monotonic stack finds the nearest smaller bars on both sides, enabling O(n) area computation.