What is a monotonic stack
What is a monotonic stack? A stack that stays sorted by popping anything that would break the order, which turns every next-greater-element question into one O(n) pass. Here is how it works, with full traces and the mistakes that cost people offers.
What is a monotonic stack? It is a normal stack that refuses to hold values out of order: before you push, you pop everything that would break the sorted order. Each pop settles a question about the popped item, usually where the next larger or smaller value sits, so one pass answers it for every element.
How does a monotonic stack work?
A monotonic stack works by comparing each incoming element with the top of the stack and popping while the order would be violated, so the stack stays sorted and every pop resolves one waiting element. Nothing about the data structure itself is special. It is a list you only touch at one end. The monotonic part is a discipline you enforce in the loop.
The framing I use is a pile of unpaid invoices. Every element on the stack is an invoice that has not yet been covered by a bigger payment. A new number arriving is a payment. It settles the most recent invoices first, and because the pile is kept in decreasing order, the top invoices are the smallest ones. So a payment clears from the top and stops the instant it meets an invoice it cannot cover. Everything deeper in the pile is larger still, so nothing below needs checking. That single observation is the whole algorithm, and it is why the stack can skip work that a naive scan would repeat.
Here is the classic first problem, restated in my own words. You get a list of daily temperatures. For each day, report how many days you must wait until a strictly warmer day, or 0 if none ever comes. For the eight days 73, 74, 75, 71, 69, 72, 76, 73 the answer is 1, 1, 4, 2, 1, 1, 0, 0.
def days_until_warmer(temps):
ans = [0] * len(temps)
stack = [] # indices; temperatures strictly decrease bottom to top
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
ans[j] = i - j
stack.append(i)
return ansTrace it by hand once, because the trace is where the idea becomes obvious. The stack holds indices, and I write the temperatures beside them.
- Day 0 (73): stack is empty, push 0. Stack: [0].
- Day 1 (74): 73 is colder, so pop day 0 and record 1 - 0 = 1. Push 1. Stack: [1].
- Day 2 (75): pop day 1 (74), record 1. Push 2. Stack: [2].
- Day 3 (71): 75 is warmer than 71, so nothing pops. Push 3. Stack: [2, 3].
- Day 4 (69): nothing pops. Push 4. Stack: [2, 3, 4].
- Day 5 (72): pop day 4 (69), record 1. Pop day 3 (71), record 2. Day 2 (75) is warmer, so stop. Push 5. Stack: [2, 5].
- Day 6 (76): pop day 5 (72), record 1. Pop day 2 (75), record 4. Push 6. Stack: [6].
- Day 7 (73): 76 is warmer, nothing pops. Push 7. Stack: [6, 7].
Days 6 and 7 never get a warmer day, so they keep their default 0. Notice what the stack is at any moment: the list of days still waiting, ordered so that each waiting day is warmer than the one above it. That ordering is the invariant, and every line of the loop exists to protect it.
Why is a monotonic stack O(n) when it has a loop inside a loop?
It is O(n) because every index is pushed exactly once and popped at most once, so the total number of pops across the entire run can never exceed n, no matter how the inner while loop behaves on any single step. The nested loop looks quadratic, but the inner loop does not restart from scratch; it consumes a shared budget.
Count the operations in the example above. Eight days means eight pushes. The pops were days 0, 1, 4, 3, 5 and 2, which is six, and days 6 and 7 were left on the stack at the end. Fourteen stack operations for eight elements, and the bound is always at most 2n. This is the same style of argument covered in what is amortized time complexity: a single step can be expensive, but the expensive steps are paid for by earlier cheap ones. Pushing an element deposits one unit of future pop work, and each pop spends one.
Now scale it up. Take n = 100,000 days. The brute force approach scans right from each day until it finds a warmer one. On a strictly decreasing input, no day ever finds one, so day i scans everything after it, and the total is 100,000 times 99,999 divided by 2, which is 4,999,950,000 comparisons. CPython manages somewhere around 10 to 30 million simple loop iterations per second, so that is a few minutes. The stack version does at most 200,000 stack operations on the same input and finishes in a small fraction of a second. On a strictly decreasing input nothing ever pops during the scan, and the stack just grows to 100,000 entries, which is the memory cost you pay for the speed.
| Approach | Time | Extra space | Work at n = 100,000 | Verdict |
|---|---|---|---|---|
| Brute force scan right from each index | O(n²) worst case | O(1) | about 5 billion comparisons | Fine for n under a few thousand |
| Min-heap of unresolved elements | O(n log n) | O(n) | about 1.7 million heap steps (log₂ n is roughly 17) | Correct but does extra work |
| Monotonic stack | O(n) | O(n) | at most 200,000 stack operations | The standard answer |
| Sparse table plus binary search | O(n log n) | O(n log n) | about 1.7 million to build, 1.7 million to query | Overkill unless you need arbitrary range queries |
The heap row deserves a second look, because it shows why the stack is not just a trick. You could keep every unresolved element in a min-heap and, for each new value, pop everything smaller. That works. But the unresolved elements are already in sorted order by construction, since the invariant keeps them that way, so paying log n per operation to re-sort something already sorted is wasted effort. If you want the general comparison of when ordering machinery is worth it, when to use a heap instead of sorting covers the other side of that trade.
When should you reach for a monotonic stack?
Reach for it when the question is about the nearest element to the left or right that is larger or smaller than the current one, because that nearest relationship is exactly what a pop discovers. If a problem statement contains the words next greater, previous smaller, how far can I see, or how many consecutive days, you are probably looking at one.
The recognisable families are these.
- Next or previous greater or smaller element. The direct form, including the circular variant, where you walk the array twice.
- Spans. A stock span, or how many consecutive earlier values are at most today's value, is a previous greater element in disguise.
- Largest region bounded by smaller values. Largest rectangle in a histogram, and by extension the maximal rectangle in a binary matrix, where you run the histogram routine once per row.
- Contribution counting. Sum of subarray minimums, where each element is the minimum of a computed number of subarrays and the stack gives you the boundaries of its reign.
- Greedy removal. Remove k digits to make the smallest number, where you pop larger digits off the end as long as you still have removals left.
- Sliding window maximum. This uses a monotonic deque, because elements also expire from the front. The idea is the same, with one extra door.
The signal I trust most is the word nearest. If the problem would be satisfied by any element that beats the current one, you probably want a hash map or a sort. If it must be the closest one in position, an ordering of positions is doing the work, and a stack respects position for free because it only ever sees the most recent items on top. It also helps to compare it with sliding window and two pointers: those techniques move boundaries around a range, while the stack remembers candidates that have not found their answer yet.
Should a monotonic stack be increasing or decreasing?
Keep the stack in the order opposite to the answer you are looking for: to find the next greater element, the stack decreases from bottom to top; to find the next smaller element, it increases. The reason is that waiting elements are precisely the ones that have not met their answer, and an element still waiting for something greater must be at least as large as everything that arrived after it.
Two sentences are enough to remember it. First, ask what the unresolved elements have in common. Second, make that the invariant. For next greater, every unresolved element is greater than or equal to everything after it, otherwise one of those later elements would have resolved it. That is a decreasing stack, and you pop while the top is less than the incoming value. For next smaller, flip both. For the previous greater element you scan the same way but read the answer differently: after popping everything smaller, whatever remains on top is the previous greater, and you read it at push time instead of pop time.
That last point is a useful distinction. There are two moments you can harvest information. At pop time, the incoming value is the next greater element for the popped item. At push time, the item beneath the new element is its previous greater. Most of the confusion I see in interview solutions comes from people who half remember one of those moments and apply it at the other.
How does the largest rectangle in a histogram use a monotonic stack?
Each pop produces both boundaries of a rectangle at once: the incoming bar is the first shorter bar on the right, and the new top of the stack is the first shorter bar on the left, so the width is everything between them. That is why one pass is enough, where a direct approach would expand outward from each bar.
Restate the problem plainly. You have bars of width 1 with given heights, and you want the area of the biggest rectangle that fits entirely under the bars. For heights 2, 1, 5, 6, 2, 3 the answer is 10, which is the two bars of height 5 and 6 cut down to height 5 and spanning width 2.
def largest_rectangle(heights):
best = 0
stack = [] # indices; heights increase bottom to top
for i, h in enumerate(heights + [0]): # sentinel 0 flushes the stack
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
left = stack[-1] if stack else -1
width = i - left - 1
best = max(best, height * width)
stack.append(i)
return bestTrace it with the sentinel appended, so the loop runs for indices 0 to 6.
- i = 0 (h = 2): push. Stack: [0].
- i = 1 (h = 1): bar 0 (height 2) is taller, pop it. The stack is empty, so left is -1 and the width is 1 - (-1) - 1 = 1. Area 2. Push 1. Stack: [1].
- i = 2 (h = 5): push. i = 3 (h = 6): push. Stack: [1, 2, 3].
- i = 4 (h = 2): pop bar 3 (height 6); left is index 2, width 4 - 2 - 1 = 1, area 6. Pop bar 2 (height 5); left is index 1, width 4 - 1 - 1 = 2, area 10. Bar 1 has height 1, which is below 2, so stop. Push 4. Stack: [1, 4].
- i = 5 (h = 3): push. Stack: [1, 4, 5].
- i = 6 (sentinel 0): pop bar 5 (height 3), left is 4, width 1, area 3. Pop bar 4 (height 2), left is 1, width 6 - 1 - 1 = 4, area 8. Pop bar 1 (height 1), stack empty, width 6, area 6.
The maximum over all those areas is 10. Seven iterations, six pushes and six pops, and no bar was ever examined twice. The expand-outward version does about n² / 4 steps on a bar chart shaped like a hill, which for 100,000 bars is over two billion. I think this problem is the best single test of whether you understand the structure, because the arithmetic of the width, i - left - 1, only makes sense if you know what the stack contents mean.
What mistakes break a monotonic stack solution?
The most common failures are storing values instead of indices, mishandling equal elements, forgetting to flush the stack at the end, and picking the wrong direction. Each of these produces an answer that is plausible on small inputs and wrong on one specific shape, which is why they survive casual testing.
Storing values when you need positions. Almost every useful answer is a distance or a width, and you cannot compute either from a value. Push indices and look up the value through the array. You pay one extra array access per comparison and save yourself a rewrite.
Duplicates. Whether you pop on strictly less or less than or equal changes the meaning of the result. For a plain next greater element, strictness decides whether an equal value counts as an answer. For contribution counting it decides whether a subarray is counted once or twice. Take the sum of subarray minimums on [2, 2]. The subarrays are [2], [2] and [2, 2], each with minimum 2, so the correct total is 6. If both sides of every element extend until a strictly smaller value, each 2 claims the subarray [2, 2] and you count 8. The fix is to make one side strict and the other non-strict, so that exactly one of the two equal elements owns the tie. I have watched this single bug sink otherwise correct solutions.
Leftovers. Elements still on the stack when the loop ends have no next greater element. For the temperatures problem that is harmless because the default is already 0. For the histogram it is fatal, since those bars still define rectangles that reach the right edge. The sentinel zero at the end of the heights list is a cheap way to force a flush, and the leftover handling disappears into the main loop.
Using it where elements expire. A plain stack has no way to forget the oldest element. If the problem limits the range, say the maximum within the last k items, the front of the structure has to drop entries, and you need a deque. If you try to bolt expiry onto a stack you end up scanning, and the linear bound is gone.
Reaching for it too early. A monotonic stack answers the nearest-larger-or-smaller question. It does not answer which element is the k-th largest, or the sum over a range. For those, prefix sums and sliding windows or a heap are the right tools, and recognising the shape first saves you from forcing the wrong one.
Frequently asked questions
Is a monotonic queue the same thing as a monotonic stack?
They share the same invariant, but a monotonic queue is implemented with a deque because elements are removed from both ends: new ones are compared at the back, and expired ones leave from the front. Sliding window maximum is the standard example. If nothing ever expires, a stack is enough.
Can I use a heap instead of a monotonic stack?
Yes, a heap gives a correct answer in O(n log n), but it re-sorts data that the stack already keeps ordered for free. In an interview, the heap version is a fine first answer if you then explain why the stack reduces it to O(n) with the same idea.
How do I get better at spotting monotonic stack problems?
Work two or three problems by hand with a pen, drawing the stack after each element, until you can predict what gets popped before it happens. Then move on to a related technique that keeps candidates in a window, and the best next step is the sliding window concept page.