Overview (Monotonic Stack)
Understand the Monotonic Stack pattern for finding Next Greater/Smaller Elements.
What is a Monotonic Stack?
A Monotonic Stack is a stack where elements are always sorted (either increasing or decreasing). It allows us to solve problems related to Next Greater Element or Next Smaller Element in O(N) time.
- Monotonic Increasing:
[1, 2, 5, 8]. Used to find the Next Smaller Element. - Monotonic Decreasing:
[10, 8, 4, 1]. Used to find the Next Greater Element.
How It Works
We iterate through an array. Before pushing a new element X, we Pop all elements from the stack that violate the monotonic property.
Example (Next Greater Element):
We want a Decreasing Stack. While X is greater than the value on top, X is the "Next Greater Element" for that top: pop it and record X as its answer. Stop when the stack is empty or its top is at least X, then push X. The stack stores indices, so each answer is written back to the position it belongs to.
Interactive Visualization
Run the template below on an array: each value pops the smaller values waiting on the stack and is written in as their answer. The stack’s values always decrease from bottom to top.
Dry Run Table
Input: [2, 1, 5, 3, 6, 4]
| i | Value | Popped (answer written) | Stack after (values) | result |
|---|---|---|---|---|
| 0 | 2 | - | [2] |
[-1, -1, -1, -1, -1, -1] |
| 1 | 1 | - | [2, 1] |
[-1, -1, -1, -1, -1, -1] |
| 2 | 5 | 1 → 5, then 2 → 5 | [5] |
[5, 5, -1, -1, -1, -1] |
| 3 | 3 | - | [5, 3] |
[5, 5, -1, -1, -1, -1] |
| 4 | 6 | 3 → 6, then 5 → 6 | [6] |
[5, 5, 6, 6, -1, -1] |
| 5 | 4 | - | [6, 4] |
[5, 5, 6, 6, -1, -1] |
6 and 4 are still on the stack at the end, so they keep -1.
Edge Cases & Common Mistakes
- Decreasing input: Nothing is ever popped, and every answer stays -1.
- Equal values:
nums[top] < nums[i]is strict, so an equal value is not a next greater element. Use<=if the problem asks for greater-or-equal. - Store indices, not values: The answer has to be written to the position it belongs to.
- Next smaller instead: Flip the comparison to
>and the stack increases from bottom to top.
The Pattern Template
Template for the next greater element of every position, or -1 when there is none.
Overview (Monotonic Stack) Code
1function nextGreater(nums) {2 const stack = [];3 const result = new Array(nums.length).fill(-1);45 for (let i = 0; i < nums.length; i++) {6 while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {7 const idx = stack.pop();8 result[idx] = nums[i];9 }10 stack.push(i);11 }12 return result;13}