📉 Monotonic Stack
One-line summary: A stack that maintains a strictly increasing or decreasing order — enabling O(n) solutions for "next greater/smaller element" and span problems.
Concept
A monotonic stack is a stack where elements are always in monotonically increasing or decreasing order. When a new element violates the order, pop elements until the invariant is restored — those popped elements have found their answer.
Key insight: each element is pushed and popped at most once → O(n) total.
- Decreasing stack → used for "next greater element"
- Increasing stack → used for "next smaller element"
Diagram
Time & Space Complexity
| Operation | Time | Space |
|---|---|---|
| Build NGE array | O(n) | O(n) |
| Daily Temperatures | O(n) | O(n) |
| Largest Rectangle in Histogram | O(n) | O(n) |
Common Patterns
Pattern 1 — Next Greater Element
function nextGreaterElement(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // stores indices
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[i] > nums[stack[stack.length - 1]])
result[stack.pop()] = nums[i];
stack.push(i);
}
return result;
}
Pattern 2 — Daily Temperatures
function dailyTemperatures(temps) {
const result = new Array(temps.length).fill(0);
const stack = [];
for (let i = 0; i < temps.length; i++) {
while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
const idx = stack.pop();
result[idx] = i - idx;
}
stack.push(i);
}
return result;
}
When to Use
- Finding next/previous greater or smaller elements
- Range-based problems with comparisons
- Span and width problems (largest rectangle, trapping rain)
- Stock span problems
Pitfalls
- Storing values instead of indices (indices let you compute distances)
- Forgetting to process remaining elements left in the stack at the end
- Confusing increasing vs decreasing stack direction
Practice Problems
Related Topics
- Stack — monotonic stack is a specialised stack
- Sliding Window — sliding window maximum uses monotonic deque
← Back to Home · © sparshjaswal