Stacks and Monotonic Structures
Monotonic stacks
The unit's central idea: throw away every candidate that can never be the answer, and what remains is sorted for free.
A question about boundaries
A large family of problems asks, for each position, about the nearest position in some direction with a particular relationship to it. The nearest larger value to the left. The nearest smaller value to the right. How far you can extend before something blocks you.
The brute force scans outward from every position, which is O(n squared). The fix is not a better scan. It is noticing that most positions are permanently useless as answers and can be discarded.
Key idea
A concrete version
Here is the classic framing. Each day has a price, and the span of a day is how many consecutive days ending today had a price less than or equal to today's, counting today.
Written naively you walk backward from each day until you hit a bigger price. Written with a stack you never walk backward at all.
Why it works
The invariant, and why the pops are permanent
The stack holds indexes whose prices are strictly decreasing from bottom to top. That is the invariant, and every line exists to maintain it.
When a new price arrives that is at least as large as the price on top, that older day is popped. It is gone forever, and that is justified: any future day looking backward for a taller price will meet today first, and today is at least as tall. The popped day can never be the answer for anything again.
This is the discard argument from Unit 2 in a new costume. Then it was one pointer discarding one candidate; now it is a stack discarding many at once, for the same kind of reason.
Cost
Why a while inside a for is still linear
Each index is pushed exactly once and popped at most once. The inner loop can do a lot of work on a single iteration and cannot do more than n pops in total across the whole run.
So the whole thing is O(n) time and O(n) space. This is the third time this argument has appeared, after the run-head guard in Unit 1 and the sliding window in Unit 3. If an interviewer questions the nested loop, this is the answer, and it is worth being able to give it in one sentence.
Tip
Four questions, one template
Direction and comparison are the only things that change. Scan left to right for a previous boundary, right to left for a next one. Pop while the top is smaller for a nearest-larger question, and while the top is larger for a nearest-smaller question.
That gives four combinations and one piece of code. Rather than memorizing four snippets, write the invariant you want the stack to hold and let the comparison follow from it.
| Question | Scan direction | Pop while top is | Stack holds |
|---|---|---|---|
| Previous greater | left to right | less than or equal | decreasing |
| Previous smaller | left to right | greater than or equal | increasing |
| Next greater | right to left | less than or equal | decreasing |
| Next smaller | right to left | greater than or equal | increasing |
Key idea
Answering forward questions during a left-to-right pass
There is a second way to answer next-boundary questions without scanning backward, and it is the one most solutions use.
Scan left to right. When the incoming element pops something off the stack, the incoming element is that popped element's next-greater neighbor. So you resolve answers as you pop rather than as you push.
Anything still on the stack when the loop ends never found a boundary, so it gets whatever the problem uses for no answer.
Tip
Which formulation to reach for
The backward scan answers a next-boundary question in the order the answers are asked for. The forward scan answers them out of order, filling a results array as it goes.
The forward version is usually shorter and is what you will want for the problem below, because the thing being asked for is a distance, and distance is naturally computed at the moment the boundary is found.
Trace the monotonic stack
Run next_greater on [2, 1, 2, 4, 3]. For each step give what the stack holds after processing that index, as a list of indexes like [0, 1], and which indexes got resolved at that step, as a list like [1] or [].
This activity type is not wired up yet.
The four variants
Write two of the four boundary questions, then use one. previous_smaller returns, for each index, the index of the nearest earlier position with a strictly smaller value, or -1. next_smaller returns the nearest later position with a strictly smaller value, or the length of the list when there is none. widest_span uses both to report, for each index, how far its value extends before something smaller blocks it on either side.
Tests
print(previous_smaller([2, 1, 5, 6, 2, 3])) print(next_smaller([2, 1, 5, 6, 2, 3])) print(widest_span([2, 1, 5, 6, 2, 3]))
Output
Run the tests when you are ready.
Daily Temperatures
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.