Monotonic Stack: When to Reach for One in an Interview
A monotonic stack is a stack that you keep sorted, either strictly increasing or strictly decreasing from bottom to top, by popping off anything that breaks the order before you push a new value on. It answers a narrow but constantly recurring question: for each element in an array, what is the next element to the left or right that is bigger or smaller than it. A brute-force scan checks every later element for every index and costs O(n squared). A monotonic stack answers the same question for the entire array in a single O(n) pass, using the stack to remember the only candidates that could ever matter. What follows is how to spot a problem that wants this pattern, the two worked examples that cover both directions, the proof for why the runtime holds even though the code looks nested, and the mistakes that trip candidates up once the interviewer changes the setup slightly.
How Do You Recognize a Monotonic Stack Problem?
You recognize a monotonic stack problem when the statement asks, for every element, about the nearest element to its left or right that is bigger or smaller, or when it asks how long you have to wait before some condition improves. That second framing shows up more often in real interviews than the textbook phrasing does, because interviewers like to disguise the pattern behind a concrete scenario instead of stating it directly.
A few concrete phrases tend to show up in real monotonic stack problems:
- "For each day, how many days do you have to wait until a warmer temperature."
- "Find the next greater element to the right for every value in the array."
- "Given a row of building heights, find the largest rectangle you can draw."
- "Remove k digits from the number to make the smallest number possible."
- "Find the span of consecutive days before today with a lower stock price."
Once you catch one of those signals, the second check is whether a brute-force nested loop, comparing every element to every later element, would technically work but run in O(n squared). If the interviewer then asks for something faster, that is your confirmation, since a monotonic stack is almost always the tool they are fishing for.
What Is a Monotonic Stack, and How Does It Stay Sorted?
A monotonic stack stays sorted by enforcing one rule on every push: before adding a new element, pop everything currently on the stack that would break the required order, whether that order is increasing or decreasing. The stack itself is an ordinary list used as a LIFO structure. What makes it monotonic is the discipline applied at push time, not a different underlying data structure.
You have two choices for what to store on the stack: the values themselves, or their indices. Storing indices is the safer default, because most problems eventually ask for a distance, a day count, or the original position of the element you found, and an index gives you all three while a bare value only gives you the value. The two examples below both store indices for exactly that reason, and switching to values only makes sense when the problem genuinely never cares about position, which is rarer than it first appears.
How Do You Solve Next Greater Element With a Monotonic Stack?
You solve next greater element by walking the array left to right while keeping a decreasing stack of indices, and every time the current value is bigger than the value at the index on top of the stack, that top index has found its answer. Given an array, the goal is to return, for every index, the value of the next element to its right that is strictly greater, or negative one if none exists.
def next_greater_elements(nums):
result = [-1] * len(nums)
stack = []
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
prev_index = stack.pop()
result[prev_index] = num
stack.append(i)
return resultThe stack holds indices whose next greater element has not been found yet, and it stays in decreasing order of value from bottom to top because anything smaller than the current value gets resolved and popped before the current index is pushed. Walk the array 2, 1, 3, 2, 4 by hand once: index 0 pushes, index 1 pushes since 1 is smaller, index 2 pops both (3 beats 1 and 2) and resolves them to 3, then pushes itself, and so on. Every index that never gets popped by the time the loop ends keeps its default of negative one, since nothing later in the array ever beat it.
Why Is a Monotonic Stack O(n) Even Though the Code Looks Like Two Nested Loops?
A monotonic stack runs in O(n) because every index gets pushed onto the stack exactly once and popped at most once, so the total work across the entire run, counting every iteration of the inner while loop combined, can never exceed two operations per element. This is the part candidates fumble most, because the code has a for loop with a while loop inside it, and the instinct is to multiply the two like you would for a true nested loop.
The reasoning that actually holds is called amortized analysis, and the honest way to explain it out loud is this: a single iteration of the outer loop can trigger several pops, so that one iteration alone might look like it costs more than O(1), but each of those pops permanently removes an index from the stack, and an index that started with n slots to be popped from can only be popped once, ever. Sum the pops across the whole run and the total is bounded by n, the same as the number of pushes. Add the two together and the algorithm still does at most 2n operations, which is O(n). Interviewers who ask you to defend the complexity are checking for this exact argument, not just the memorized answer.
How Do You Solve Daily Temperatures With a Monotonic Stack?
You solve daily temperatures the same way, with a decreasing stack of indices, except the value you write into the result array is the distance between indices instead of the temperature itself. Given a list of daily temperatures, return for each day how many days you would have to wait until a warmer temperature.
def daily_temperatures(temperatures):
result = [0] * len(temperatures)
stack = []
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
prev_index = stack.pop()
result[prev_index] = i - prev_index
stack.append(i)
return resultThe mechanics are identical to next greater element. The only change is what you do at resolution time, which is a distance calculation instead of a value lookup. That similarity is the point: once you recognize the shape, most monotonic stack problems are the same loop with a different payload written at the moment an element gets popped, and practicing that substitution is more valuable than memorizing each problem separately.
Increasing or Decreasing Stack: How Do You Pick the Direction?
You pick a decreasing stack when the problem asks for the next greater element, and an increasing stack when it asks for the next smaller element, because the stack's order needs to match what would disqualify an element from being the answer. A decreasing stack pops while the top of the stack is smaller than the current value, since anything smaller than the current value has just found something bigger and is done. An increasing stack pops on the opposite condition, while the top of the stack is bigger than the current value.
Largest rectangle in histogram and stock span both use an increasing stack, because both need the previous smaller element rather than the next greater one. For the histogram problem, an increasing stack of bar heights lets you compute, at the moment a shorter bar forces a pop, the width of the rectangle that the popped bar could have spanned before something shorter cut it off. If you find yourself unsure which direction a new problem wants, restate the question as "next greater" or "next smaller" in your own words first. Getting that restatement right decides the whole direction before you write a line of code.
What Mistakes Sink a Monotonic Stack Answer in an Interview?
Storing values instead of indices is the most common mistake, and it usually only shows up once the interviewer asks a follow-up that needs a distance or a position, at which point the candidate realizes the stack threw away information they now need and has to restart. Default to storing indices unless you have a specific reason not to, since you can always look up the value from the index but not the reverse.
Getting the comparison operator backward is the second common failure, popping when a value is equal instead of only when it is smaller, or the reverse. That single detail decides how duplicate values are treated, and a problem that asks for the next strictly greater element behaves differently from one that allows equal values to count, so read the problem statement for the word "strictly" before choosing the operator.
Forgetting that elements left on the stack when the loop ends need a default value is the third mistake, and it is easy to miss because the code runs without error, it just returns wrong answers for whichever indices never got popped. Every index that stays on the stack after the last iteration never found a next greater or next smaller element in the array, so it should keep whatever default the problem specifies, usually negative one or zero, and that default belongs in the result array's initialization, not as an afterthought at the end.
Flipping the direction partway through a problem that actually needs two passes, one left to right and one right to left, is the fourth mistake, and it shows up in problems like a version of next greater element that wraps around a circular array. Recognizing that a problem needs two passes instead of one is itself part of the pattern-matching skill this section is meant to build.
How Is a Monotonic Stack Different From a Regular Stack, Sliding Window, or Two Pointers?
A monotonic stack differs from a regular stack in that it enforces an order invariant on every push, while a plain stack has no ordering guarantee at all and is just a LIFO structure. A regular stack answers questions about nesting and matching, like valid parentheses, where order genuinely does not matter beyond last in, first out.
It also differs from sliding window and two pointers, even though all three run in a single O(n) pass and can look similar on the page. Our sliding window guide tracks a contiguous range and asks what the best range looks like as it grows and shrinks, which needs running state about everything currently inside the window. Our two pointers guide compares two boundary values directly with no state about what sits between them. A monotonic stack does neither: it keeps a partial history of unresolved elements and resolves them one at a time as better candidates arrive, which is a fundamentally different kind of bookkeeping from a window or a pair of boundaries, even though the final complexity often comes out the same.
What Should You Say Out Loud While You Solve One?
Name the direction before you write any code, saying something like "this asks for the next greater element, so I need a decreasing stack" and give the one-sentence reason a nested loop would be slower. That sentence signals to the interviewer that you matched the pattern deliberately instead of guessing your way into a working stack.
As you write the loop, narrate what gets stored, index or value, and why. Trace through a short example by hand once the code is on the screen, including what happens to any indices still on the stack when the array ends. Then state the complexity argument from the amortized analysis section above, since claiming O(n) without being able to defend it usually invites the exact follow-up question that catches candidates off guard. Our guide to analyzing time complexity goes deeper on how interviewers probe complexity claims beyond the first answer you give.
Which Practice Problems Build the Pattern, and Where Does This Fit Into Your Prep?
A good practice set moves through both directions and one problem that combines the pattern with something else, in an order that adds one new piece at a time. Start with next greater element to learn the decreasing-stack mechanics, then daily temperatures to practice writing a distance into the result array instead of a value. Largest rectangle in histogram is the natural next step, since it uses an increasing stack and adds a width calculation on top of the core loop. Online stock span and remove k digits round out the set by applying the same mechanics to a running count and to digit removal instead of array lookups.
Our curated question bank pulls from real onsite reports rather than a static public list, so the monotonic stack problems you find there reflect what companies are actually asking in current loops. And if you want the full map of how this pattern relates to sliding window, two pointers, binary search, and the rest of the core set, our guide to spotting patterns before you code covers that signal-recognition habit across every pattern this site treats in depth, with this guide filling in the one pattern it does not cover on its own.
Frequently Asked Questions
What is a monotonic stack used for?
A monotonic stack is used to answer next-greater-element and next-smaller-element questions, along with anything that can be reframed the same way, such as how many days until a warmer temperature or how far back a lower stock price occurred. It solves these in a single O(n) pass instead of the O(n squared) a brute-force nested loop would need.
Do I store values or indices in a monotonic stack?
Store indices by default, since most monotonic stack problems eventually ask for a distance, a day count, or a position rather than just the value itself, and an index lets you look up the value at any time while a bare value cannot give you the position back. Only store raw values when the problem genuinely never needs position, which is the less common case.
Is a monotonic stack the same as a regular stack?
A monotonic stack is not the same as a regular stack. A regular stack has no ordering guarantee beyond last in, first out, while a monotonic stack enforces a strict increasing or decreasing order by popping anything that would break that order before every push. The extra discipline at push time is what makes it monotonic, not a different underlying data structure.
What is the time complexity of a monotonic stack solution?
Monotonic stack solutions run in O(n) time and O(n) space in the worst case, even though the code has a loop inside a loop. Each element gets pushed once and popped at most once across the entire run, so the total work stays bounded by a constant multiple of n rather than growing with the square of n.
How do I know whether to use an increasing or decreasing stack?
Restate the problem as either "next greater element" or "next smaller element" in your own words first. A decreasing stack answers next greater element questions, popping while the top is smaller than the current value. An increasing stack answers next smaller element questions, popping while the top is bigger than the current value.
What's a good first monotonic stack problem to practice?
Start with next greater element to learn the decreasing-stack mechanics on a simple value lookup, then move to daily temperatures once that feels automatic, since it only changes what gets written at resolution time from a value to a distance. Save largest rectangle in histogram for after both of those, since it adds a width calculation on top of the same core loop.