One question, many disguises#
These five questions look unrelated:
- For each number, what is the next larger one to its right?
- How many days until it gets warmer?
- How many days has this price been the highest?
- What is the largest rectangle in a histogram?
- How much rainwater sits between these bars?
They are the same question. Every one of them is asking, for each position, where is the nearest value bigger (or smaller) than mine? Once you can answer that in one pass, all five fall out.
Why the obvious way is too slow#
Looking right from each position until you find something larger is two nested loops. On [5, 4, 3, 2, 1] it never finds anything and does the full scan every time: n squared comparisons. Ten thousand numbers is fine. A hundred thousand is ten billion, and the judge stops you long before that.
What the slow version is throwing away#
Walk [2, 7, 3, 5] and watch what happens when the 7 arrives.
The 2 is answered: 7 is the first larger value to its right. But notice something stronger. The 2 can now be forgotten entirely. Any future value that would have been the answer for 2 is standing behind 7, and 7 got there first. The 2 will never be needed again.
That is the whole trick. Once a value is answered, it leaves. Once a value is overtaken by a bigger one, it can never be the answer for anything further right, so it leaves too.
What remains is a stack whose values are always in order, largest at the bottom. That is what monotonic means, and it is not something you enforce: it is simply what is left once you remove everything that cannot matter.
The shape#
for each position i:
while the stack is not empty and stack.top loses to nums[i]:
settle stack.pop() using i
push i
Only two decisions change between problems:
| Decision | Next greater | Stock span | Histogram |
|---|---|---|---|
| what "loses" means | top value is smaller | top price is at or below today | top bar is taller |
| what to settle | the answer is nums[i] | span is the distance | area is height times width |
Everything else is identical. Positions go on the stack, not values, because most of these problems need the distance and the index is what gives you that.
Why it is one pass#
Each position is pushed exactly once and popped at most once. The inner while can run many times on one step, but across the whole run it cannot run more times than there were pushes. So the total work is proportional to n, even though the code has a loop inside a loop.
This is worth recognising in an interview. "There is a nested loop, so it is n squared" is wrong here, and being able to say why is the difference between knowing the trick and understanding it.
A flush at the end#
When the walk finishes, anything still on the stack was never answered. For "next greater" those answers are -1. For the histogram, they are rectangles that reach the far end, and the neatest way to settle them is to pretend there is one more bar of height zero, shorter than everything, which empties the stack on the last step.
Where it does not apply#
The stack works because an answered item is gone for good. If a problem lets an item be the answer for something and then the answer for something else with different rules, the ordering breaks and this is the wrong tool. Range maximum queries, for instance, want a segment tree, not a stack.
Practice in order#
- Next greater element for the bare pattern.
- Daily temperatures for the same thing measured in distance.
- Stock span for the mirror image, looking left instead of right.
- Largest rectangle for using both sides at once.
- Trapping rainwater, which can be done with this stack but is neater with two pointers. Solving it both ways is the best time you will spend on this page.