A monotonic stack is just a regular stack with one rule: the elements inside are always in sorted order (either increasing or decreasing from bottom to top). Whenever we push a new element, we pop off anything that violates this order.
In simple language, it’s a stack that stays sorted at all times. We enforce the ordering ourselves during push operations.
Why It Matters
Monotonic stacks turn O(n²) “find the next greater/smaller element” problems into O(n). That’s a massive improvement. They show up in a surprising number of interview problems: stock prices, temperatures, histograms, and more.
Two Flavors
Monotonically increasing (bottom to top): each element is larger than the one below it. We pop off elements that are greater than or equal to the new one.
Monotonically decreasing (bottom to top): each element is smaller than the one below it. We pop off elements that are less than or equal to the new one.
The key insight: each element gets pushed once and popped at most once. So even though we have a while loop inside a for loop, the total work is O(n).
Pattern: Next Greater Element
We covered this briefly in the stacks topic. Let’s formalize the monotonic stack approach. We use a decreasing stack (from bottom to top) and iterate left to right.
When we’re about to push an element, everything we pop off has found its “next greater element” — it’s the element we’re about to push.
// Next greater element using monotonic stack -- O(n)
function nextGreaterElement(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // stores indices, values decrease bottom to top
for (let i = 0; i < nums.length; i++) {
// pop all smaller elements -- current num is their "next greater"
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
}
// [2, 1, 3, 2, 4] -> [3, 3, 4, 4, -1]# Next greater element using monotonic stack -- O(n)
def next_greater_element(nums):
result = [-1] * len(nums)
stack = [] # stores indices, values decrease bottom to top
for i in range(len(nums)):
# pop all smaller elements -- current num is their "next greater"
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)
return result
# [2, 1, 3, 2, 4] -> [3, 3, 4, 4, -1]// Next greater element using monotonic stack -- O(n)
static int[] nextGreaterElement(int[] nums) {
int[] result = new int[nums.length];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // stores indices
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
}
// [2, 1, 3, 2, 4] -> [3, 3, 4, 4, -1]Daily Temperatures
Given daily temperatures, find how many days we need to wait for a warmer day. This is just “next greater element” but we return the distance instead of the value.
Example: [73, 74, 75, 71, 69, 72, 76, 73] returns [1, 1, 4, 2, 1, 1, 0, 0].
// Daily temperatures -- how many days until warmer?
function dailyTemperatures(temps) {
const result = new Array(temps.length).fill(0);
const stack = []; // stores indices of days waiting for a warmer day
for (let i = 0; i < temps.length; i++) {
while (stack.length && temps[stack[stack.length - 1]] < temps[i]) {
const prevDay = stack.pop();
result[prevDay] = i - prevDay; // distance to warmer day
}
stack.push(i);
}
return result;
}# Daily temperatures -- how many days until warmer?
def daily_temperatures(temps):
result = [0] * len(temps)
stack = [] # stores indices of days waiting for a warmer day
for i in range(len(temps)):
while stack and temps[stack[-1]] < temps[i]:
prev_day = stack.pop()
result[prev_day] = i - prev_day # distance to warmer day
stack.append(i)
return result// Daily temperatures -- how many days until warmer?
static int[] dailyTemperatures(int[] temps) {
int[] result = new int[temps.length];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < temps.length; i++) {
while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
int prevDay = stack.pop();
result[prevDay] = i - prevDay; // distance to warmer day
}
stack.push(i);
}
return result;
}Notice how similar this is to the next greater element problem? Same pattern, different return value. That’s the beauty of monotonic stacks — once we know the pattern, many problems look the same.
Largest Rectangle in Histogram
This is a harder problem, but it’s a classic monotonic stack application. Given an array of bar heights, find the area of the largest rectangle we can form.
The key insight: for each bar, we need to know how far it can extend to the left and right without hitting a shorter bar. A monotonic increasing stack gives us exactly that.
// Largest rectangle in histogram -- O(n)
function largestRectangleArea(heights) {
const stack = []; // stores indices, heights increase bottom to top
let maxArea = 0;
const n = heights.length;
for (let i = 0; i <= n; i++) {
const h = i === n ? 0 : heights[i]; // sentinel value at end
while (stack.length && heights[stack[stack.length - 1]] > h) {
const height = heights[stack.pop()];
// width = distance between current i and new stack top
const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}# Largest rectangle in histogram -- O(n)
def largest_rectangle_area(heights):
stack = [] # stores indices, heights increase bottom to top
max_area = 0
n = len(heights)
for i in range(n + 1):
h = heights[i] if i < n else 0 # sentinel value at end
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i - stack[-1] - 1 if stack else i
max_area = max(max_area, height * width)
stack.append(i)
return max_area// Largest rectangle in histogram -- O(n)
static int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int maxArea = 0;
int n = heights.length;
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i]; // sentinel value at end
while (!stack.isEmpty() && heights[stack.peek()] > h) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}The sentinel value (0 at the end) forces us to process all remaining bars in the stack. Without it, we’d need a separate loop after the main iteration.
Choosing the Right Monotonic Stack
| Problem Type | Stack Order | Direction |
|---|---|---|
| Next greater element | Decreasing (bottom to top) | Left to right |
| Next smaller element | Increasing (bottom to top) | Left to right |
| Previous greater element | Decreasing | Right to left |
| Previous smaller element | Increasing | Right to left |
When to Think Monotonic Stack
The signal is usually one of these:
- “Find the next greater/smaller element”
- “How many days until…”
- “Largest rectangle / container”
- Any problem where we need to efficiently look at nearby elements that satisfy a comparison
If a brute force approach uses nested loops where the inner loop searches for the next bigger/smaller value, that’s almost certainly a monotonic stack problem. We go from O(n²) to O(n) — each element is pushed and popped at most once.