Algorithms from zero
The monotonic stack
Last lesson you learned about queues and deques. Today you will learn about a powerful variant of the stack: the monotonic stack. This is a stack that maintains a special property: the elements inside are kept in a sorted order (either increasing or decreasing). When you want to push a new element, you first pop out any elements that break this order. The key insight: this breaks the classic “last pushed is first popped” rule, yet each element is still pushed and popped at most once, giving O(n) total time. The canonical problem is finding the next greater element (NGE) — for each item in an array, find the next item to its right that is larger. A naive solution is O(n²), but monotonic stack solves it in O(n).
After this lesson you can explain what a monotonic stack is and how the push-with-pop invariant maintains order, implement the monotonic-stack algorithm to find the next greater element for each item in O(n) time, trace through a concrete example step by step, understand why each element is pushed and popped at most once and how that guarantees O(n) total time, and recognize other problems (next smaller, previous greater) that fit the monotonic-stack pattern.
What is a monotonic stack?
A monotonic stack is a variant of the regular stack that maintains a strict ordering among its elements. Instead of allowing any element to be pushed, you enforce a rule: elements must be in increasing order (or decreasing order, depending on your choice). When a new element arrives:
- While the stack is not empty and the top violates the order, pop the top.
- Push the new element.
The result: after every push, the stack contents form a sorted sequence.
Increasing vs. decreasing:
- Monotonic increasing: stack = [1, 3, 5, 7]. When you push 2, pop 7, 5, 3 first. Then push 2 → [1, 2].
- Monotonic decreasing: stack = [7, 5, 3, 1]. When you push 6, pop 5, 3, 1 first. Then push 6 → [7, 6].
The next-greater-element problem:
Given an array, for each element, find the next element to its right that is larger. If no such element exists, return -1.
Example: arr = [2, 1, 2, 4, 3]
- Element 2 (index 0): next greater is 4. Answer: 4.
- Element 1 (index 1): next greater is 2. Answer: 2.
- Element 2 (index 2): next greater is 4. Answer: 4.
- Element 4 (index 3): no greater element to the right. Answer: -1.
- Element 3 (index 4): no greater element to the right. Answer: -1.
Naive approach: O(n²)
For each element, scan all elements to its right to find the next greater. Worst case: n * n = O(n²).
function nextGreaterBrute(arr) {
const result = new Array(arr.length);
for (let i = 0; i < arr.length; i++) {
result[i] = -1; // Default: no greater element
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] > arr[i]) {
result[i] = arr[j];
break;
}
}
}
return result;
}This is slow. As you read more elements, the nested loop cost explodes.
Monotonic-stack approach: O(n)
Insight: process the array from right to left. Keep a monotonic decreasing stack of elements seen so far. For each new element:
- Pop all elements from the stack that are ≤ the new element (they cannot be “next greater” for anything).
- If the stack is not empty, the top is the next greater element for the current element.
- Push the current element onto the stack.
Why does this work? The stack acts as a “candidate list.” By the time you visit an element, the stack already contains all possible candidates to its right, pre-filtered and sorted.
Why is it O(n)? Each element is pushed once and popped at most once. So total operations = O(2n) = O(n).
Monotonic-stack solution for next greater element:
function nextGreater(arr) {
const stack = []; // Stack of indices (not values)
const result = new Array(arr.length).fill(-1);
// Process from right to left
for (let i = arr.length - 1; i >= 0; i--) {
// Pop elements that are <= current element
while (stack.length > 0 && arr[stack[stack.length - 1]] <= arr[i]) {
stack.pop();
}
// If stack is not empty, top is the next greater element
if (stack.length > 0) {
result[i] = arr[stack[stack.length - 1]];
}
// Push current index
stack.push(i);
}
return result;
}Why we store indices, not values:
We push indices onto the stack so that later, when we need the actual next greater value, we can index into the array. This pattern is common in monotonic-stack problems.
Try it in the interactive runner:
Let us trace the next-greater-element algorithm on the array [2, 1, 2, 4, 3].
We process from right to left (i = 4, 3, 2, 1, 0). At each step, we pop indices whose values are ≤ the current value, then push the current index.
1
for (let i = arr.length - 1; i >= 0; i--) {
2
while (stack.length > 0 && arr[stack[stack.length - 1]] <= arr[i]) {
3
stack.pop();
4
}
5
if (stack.length > 0) {
6
result[i] = arr[stack[stack.length - 1]];
7
}
8
stack.push(i);
9
}
Time complexity: O(n)
Each element is pushed onto the stack exactly once. Each element is popped at most once. Total operations = pushes + pops ≤ 2n. So time complexity is O(n).
This is a dramatic improvement over the naive O(n²) approach.
Space complexity: O(n)
In the worst case, the stack stores all n indices (e.g., if the array is in increasing order). The result array also uses O(n) space.
Comparison with naive approach:
| Approach | Time | Space |
|---|---|---|
| Nested loop (naive) | O(n²) | O(n) |
| Monotonic stack | O(n) | O(n) |
For large arrays, monotonic stack is orders of magnitude faster.
In the monotonic-stack approach for next greater element, we process the array from which direction?
When we see a new element in the monotonic stack for next-greater-element, which elements do we pop?
What is stored on the monotonic stack: array values or array indices?
For the array [1, 2, 3, 4], what is the next greater element for index 0?
Why is the monotonic-stack approach O(n) instead of O(n²)?
Edge cases
What if there are equal elements? The problem statement usually says “next greater,” which means strictly greater (not equal). In the code, we use <= in the pop condition, which ensures that equal elements are also popped. If you need “next greater-or-equal,” change <= to <.
Common mistake
“Monotonic stack = always increasing.” Wrong. A monotonic stack can be increasing or decreasing. For next-greater-element, we use a decreasing stack (so that the top is always the smallest candidate to the right, i.e., the next greater). For next-smaller-element, we use an increasing stack.
More practice
Follow-up problems:
- Next smaller element (NSE): Use a monotonic increasing stack instead.
- Previous greater element (PGE): Process left to right with a monotonic decreasing stack, tracking indices to the left.
- Largest rectangle in histogram: A classic monotonic-stack problem where you pop when height decreases, computing areas as you go. The pattern is similar: maintain order and pop to detect when a constraint is violated.
Why does the monotonic-stack approach work for finding the next greater element?
The monotonic stack: a sorted candidate list
-
What is it: A stack that maintains elements in sorted order (increasing or decreasing). When you push a new element, you first pop elements that break the order.
-
The invariant: After each push, the stack is sorted (e.g., decreasing for NGE). This property ensures you only keep relevant candidates.
-
Next greater element: Process the array right-to-left. Pop indices whose values are ≤ current. The top is the answer. Push the current index. Result: O(n) instead of O(n²).
-
Why O(n): Each element is pushed once and popped once. Total operations = O(2n) = O(n).
-
Increasing vs. decreasing: For next-greater, use decreasing. For next-smaller, use increasing. The choice depends on which direction you need.
-
Real-world applications: Stock span, largest rectangle in histogram, trapping rain water, daily temperatures. Any problem asking for the next/previous element satisfying a constraint is a candidate for monotonic stack.
-
Key insight: The stack is not a general-purpose container; it is a tool for efficiently filtering and ordering candidates. The sorted invariant is what makes the magic work.
You now have the tools to solve problems that naively seem O(n²) but are actually O(n) with a cleverly maintained stack.