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.

1def price_spans(prices):2    spans = []3    stack = []                       # indexes, prices strictly decreasing4 5    for i, price in enumerate(prices):6        while stack and prices[stack[-1]] <= price:7            stack.pop()              # that day can never block anything again8        previous_taller = stack[-1] if stack else -19        spans.append(i - previous_taller)10        stack.append(i)11 12    return spans13 14print(price_spans([100, 80, 60, 70, 60, 75, 85]))

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.

1def next_greater(values):2    answers = [-1] * len(values)3    stack = []                       # indexes waiting for their answer4 5    for i, value in enumerate(values):6        while stack and values[stack[-1]] < value:7            answers[stack.pop()] = value      # i resolves that waiting index8        stack.append(i)9 10    return answers11 12print(next_greater([2, 1, 2, 4, 3]))

Trace it· 8 min

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 [].

i	value	resolved this step	stack after
0	2
1	1
2	2
3	4

Code lab· 25 min

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.

solution.py

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 tests to see output.

Problem· 22 min

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.

A question about boundaries

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.

1def price_spans(prices):2 spans = []3 stack = [] # indexes, prices strictly decreasing4 5 for i, price in enumerate(prices):6 while stack and prices[stack[-1]] <= price:7 stack.pop() # that day can never block anything again8 previous_taller = stack[-1] if stack else -19 spans.append(i - previous_taller)10 stack.append(i)11 12 return spans13 14print(price_spans([100, 80, 60, 70, 60, 75, 85]))

1def next_greater(values):2 answers = [-1] * len(values)3 stack = [] # indexes waiting for their answer4 5 for i, value in enumerate(values):6 while stack and values[stack[-1]] < value:7 answers[stack.pop()] = value # i resolves that waiting index8 stack.append(i)9 10 return answers11 12print(next_greater([2, 1, 2, 4, 3]))

value

resolved this step

stack after