Monotonic Stack Patterns for Coding Interviews

A monotonic stack is a plain stack with one rule: the values inside it are always kept in increasing (or decreasing) order. That simple invariant turns many "find the next bigger/smaller element" problems from O(n^2) brute force into a clean O(n) pass, which is exactly the improvement interviewers are waiting for you to find. The core idea Walk through the array once. Before pushing the current element, pop everything that breaks the ordering. Each popped element has just found its answer: the current element is its "next greater" (or "next smaller") value. Because every index is pushed once and popped at most once, the total work is linear. Template: next greater element def next_greater(nums): res = [-1] * len(nums) stack = [] # holds indices, values decreasing for i, x in enumerate(nums): while stack and nums[stack[-1]] < x: res[stack.pop()] = x stack.append(i) return res Store indices rather than values. Indices let you compute distances (days until a warmer temperature) and widths (largest rectangle), and you can always look up the value. How to choose increasing vs. decreasing - Looking for the next GREATER element? Keep the stack DECREASING; a bigger value pops smaller ones. - Looking for the next SMALLER element? Keep the stack INCREASING; a smaller value pops bigger ones. - Need the PREVIOUS greater/smaller instead? After popping, whatever remains on top of the stack is the answer for the current element. Problems that use this pattern 1. Daily Temperatures: for each day, how many days until a warmer one? Next greater element, answer is i - popped_index. 2. Next Greater Element II (circular array): loop over the array twice (i from 0 to 2n-1, use i % n) and only push during the first pass. 3. Largest Rectangle in Histogram: keep an increasing stack of bar indices. When a shorter bar arrives, pop and compute the area using the popped height and the width between the new top and the current index. Append a sentinel 0 at the end to flush the stack. 4. Trapping Rain Water: a decreasing stack finds "valleys"; when a taller bar arrives, pop the bottom and add water bounded by the new top and the current bar. 5. Online Stock Span: a decreasing stack of (price, span) pairs, merging spans as smaller prices are popped. 6. Remove K Digits / Smallest Subsequence: an increasing stack greedily removes larger digits that appear before smaller ones. Common mistakes - Using < when the problem needs <= (or vice versa). Ask yourself how equal values should be treated and test a case with duplicates. - Forgetting elements left in the stack at the end. They usually mean "no answer" (-1) or need a sentinel to flush them. - Mixing up values and indices halfway through the code. How to explain it in an interview Start with the brute force: "For each element I could scan to the right, which is O(n^2)." Then point out the waste: "Once a bigger element appears, all smaller ones before it are resolved and never matter again." That observation is the monotonic stack. Finish with the amortized argument: each index is pushed and popped at most once, so the solution is O(n) time and O(n) space. Practicing the explanation matters as much as the code. Linkjob AI (https://linkjob.ai) provides real-time help during job interviews and technical interviews, helping you keep this brute force to optimization narrative structured while you are live. Use it to support preparation you have already done. Takeaway: whenever a problem asks for the nearest larger or smaller element on either side, reach for a monotonic stack.