Some coding interview questions look innocent — “find the next greater element,” “compute the largest rectangle in a histogram” — but the naive solutions balloon into nested loops and time-limit failures. The monotonic stack is the pattern that quietly solves an entire family of these problems in linear time. It’s less famous than dynamic programming or two pointers, which is exactly why recognizing it gives you an edge. This guide explains what a monotonic stack is, when to reach for it, and how to apply it with worked examples you can practice today.
What a Monotonic Stack Is
A monotonic stack is an ordinary stack with one extra rule: you keep its elements sorted, either increasing or decreasing, as you push. Before pushing a new element, you pop everything that would violate that order. That single discipline is what gives the pattern its power — each element is pushed and popped at most once, so a loop that looks nested actually runs in O(n) total.
There are two flavors. A monotonically decreasing stack keeps larger elements near the bottom and is used to find the next (or previous) greater element. A monotonically increasing stack keeps smaller elements near the bottom and finds the next smaller element. The direction you traverse the array — left to right or right to left — combined with the stack direction determines exactly which relationship you compute.
The Signals That Point to a Monotonic Stack
You rarely get a question titled “use a monotonic stack.” Instead, watch for these phrasings, which almost always map to the pattern:
- “Find the next greater / next smaller element” for each item.
- “How many days until a warmer temperature?”
- “Largest rectangle in a histogram” or “maximal rectangle” in a matrix.
- “Trapping rain water” between bars.
- “Remove k digits to make the smallest number” or “build the smallest/largest sequence.”
The common thread: for each element you need to know the nearest element on one side that is bigger or smaller. Whenever that relationship appears, a stack that maintains order will usually beat a nested loop.
Worked Example 1: Next Greater Element
Given an array, return an array where each position holds the next element to the right that is strictly greater, or -1 if none exists. The brute force compares every pair — O(n²). A decreasing monotonic stack does it in one pass.
Idea: iterate left to right, keeping a stack of indices whose “next greater” is still unknown. When the current value is greater than the value at the top index, that current value is the answer for the top — so pop and record it.
int[] nextGreater(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
Deque<Integer> stack = new ArrayDeque<>(); // holds indices
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
res[stack.pop()] = nums[i];
}
stack.push(i);
}
return res;
}Each index enters and leaves the stack once, so the runtime is O(n) with O(n) space. When you explain this in an interview, emphasize that the inner while loop does not make it quadratic — that amortized-analysis insight is exactly what interviewers want to hear.
Worked Example 2: Daily Temperatures
Given daily temperatures, return how many days you’d wait for a warmer day. It’s the “next greater element” idea, but the answer is a distance rather than the value, so the stack stores indices.
int[] dailyTemperatures(int[] temps) {
int n = temps.length;
int[] res = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
int prev = stack.pop();
res[prev] = i - prev;
}
stack.push(i);
}
return res;
}Same skeleton, different bookkeeping. Recognizing that two differently worded questions share one template is the pattern-recognition skill that separates fast candidates from slow ones.
Worked Example 3: Largest Rectangle in a Histogram
This is the classic hard application. Given bar heights, find the area of the largest rectangle. The insight: for each bar, the widest rectangle using that bar’s height extends until it hits a shorter bar on each side — precisely a “previous smaller” and “next smaller” query, which a monotonic increasing stack answers in one pass.
int largestRectangleArea(int[] heights) {
int n = heights.length, maxArea = 0;
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!stack.isEmpty() && h < heights[stack.peek()]) {
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 trailing sentinel (h = 0 when i == n) flushes the stack cleanly at the end — a small trick worth remembering, because forgetting it is the most common bug here.
A Reusable Template
Most monotonic stack solutions follow the same shape, which you can memorize as a starting point and adapt:
- Decide what the stack stores — usually indices, so you can compute both distances and values.
- Choose the direction: iterate left to right for “next” relationships, right to left for “previous” ones.
- Choose the comparison: pop while the top violates the order you want to maintain.
- Do your bookkeeping at the moment you pop — that is when a resolved relationship is discovered.
- Consider a sentinel value to flush any leftover stack entries at the end.
How to Present It in the Interview
Start by stating the brute-force O(n²) approach so the interviewer sees you understand the baseline. Then name the observation that unlocks the pattern: “For each element I only need the nearest greater element on one side, so I can maintain a stack of candidates.” Walk through a tiny example — three or four values — narrating each push and pop. Finish with the amortized-complexity argument: every element is pushed and popped once, giving O(n). That closing point demonstrates depth and is often what earns the “strong hire” note.
Common Mistakes to Avoid
Three errors show up repeatedly. First, storing values when you actually need indices, which makes distance questions like Daily Temperatures impossible to answer. Second, using the wrong strict-versus-non-strict comparison (> vs >=), which quietly breaks handling of duplicate values — always clarify with the interviewer whether equal elements count. Third, forgetting to drain the stack at the end, leaving some elements without answers. A sentinel or a final cleanup loop prevents that.
Start Practicing Today
The monotonic stack is a small idea with an outsized return: it converts a whole category of nested-loop problems into elegant linear-time solutions, and it appears often enough to be worth deliberate practice. Work through Next Greater Element, Daily Temperatures, Largest Rectangle in a Histogram, and Trapping Rain Water in that order — they build on one another naturally. For each, write down what the stack stores and which direction you traverse before you code. Do that consistently and the pattern will become automatic well before your next interview.
For more structured interview preparation and practice, explore Niraswa AI.
