Monotonic Stacks in Coding Interviews: Next Greater Element and Friends

The monotonic stack is one of those techniques that seems magical the first time you see it and obvious the tenth time. It solves a family of interview problems that otherwise look like they need O(n^2) nested loops: "next greater element", "daily temperatures", "largest rectangle in histogram", "trapping rain water", "stock span", and "sum of subarray minimums". Learning it well gives you a reliable O(n) answer to all of them. What a monotonic stack is A monotonic stack is an ordinary stack that you keep in sorted order, either increasing or decreasing, as you scan the array. Before pushing a new element, you pop every element that would break the order. The popping step is where the useful work happens: when an element gets popped, you have just found the answer for it. Next greater element For each element, find the first element to its right that is larger. Scan left to right with a stack of indices whose values are decreasing. When the current value is larger than the value at the top of the stack, the current element is the "next greater" for that top index. Pop it, record the answer, and repeat. Then push the current index. stack = [] answer = [-1] * n for i, x in enumerate(nums): while stack and nums[stack[-1]] < x: answer[stack.pop()] = x stack.append(i) Every index is pushed once and popped at most once, so the total work is O(n) despite the nested while loop. Explaining this amortized argument is one of the things interviewers listen for. Daily temperatures This is the same problem, except the answer is the distance in days rather than the value. Record i - popped_index instead of x. Choosing increasing or decreasing - Looking for the next greater element: keep a decreasing stack. - Looking for the next smaller element: keep an increasing stack. - Looking for previous greater or smaller: either scan right to left, or read the answer from whatever remains on the stack just before you push. A quick way to remember it: the stack holds elements still waiting for their answer, and the current element resolves the ones it beats. Largest rectangle in histogram For each bar, the largest rectangle using that bar as the shortest height extends until the nearest smaller bar on each side. Use an increasing stack. When a shorter bar arrives, pop taller bars; for each popped bar, the current index is its right boundary and the new stack top is its left boundary. Area equals height times (right - left - 1). Append a zero-height sentinel at the end so every bar gets popped. Trapping rain water There is a two-pointer solution, but the stack solution is a good demonstration of the pattern. Keep a decreasing stack of indices; when a taller bar arrives, pop the bottom of a "valley" and compute the water bounded by the new top and the current bar. Circular arrays For "next greater element II" on a circular array, loop through the indices twice (i from 0 to 2n - 1, using i % n) and only push during the first pass. This simulates wrap-around without copying the array. Common bugs - Storing values instead of indices when you need distances or widths. - Using < when the problem needs <= for duplicates. - Forgetting the sentinel in histogram problems, which leaves bars unprocessed. - Off-by-one errors in width calculations. How to talk about it in an interview Start with brute force, then note that each element only needs the nearest larger or smaller neighbor, which is exactly what a monotonic stack maintains. State O(n) time with the amortized argument and O(n) space. Dry-run on a short array such as [2, 1, 5, 6, 2, 3], showing the stack after each step. Practice list Next greater element I and II, daily temperatures, online stock span, largest rectangle in histogram, maximal rectangle, trapping rain water, and sum of subarray minimums. During live rounds, some candidates use Linkjob AI (https://linkjob.ai), which gives real-time help during job interviews and technical interviews, to keep their reasoning organized under pressure. Once the "who is still waiting for an answer" idea clicks, these problems become fast and dependable.