Monotonic stacks: pop what the new value beats

A sensor logs the temperature once a minute. For each reading, how long until a warmer one? The direct way scans right from each reading until it meets something warmer. On a million readings that only fall, every scan runs to the end: n(n − 1)/2, about 500 billion comparisons. O(n²).

Look at the readings still waiting for an answer. From oldest to newest they never get warmer: a newer, warmer reading would already have answered the older ones. So a warm reading that arrives beats the newest waiting readings first, all at one end. Keep them on a stack: each new reading pops every reading it answers, then waits itself. That is a monotonic stack: one pass, each reading pushed once and popped at most once, and fewer than 2 million comparisons for the million readings.

next greater value

For the value at position i, the first larger value to its right; −1 (or 0 days) if there is none.

waiting

A position whose answer hasn't been found yet. The waiting positions are exactly the ones on the stack.

monotonic stack

A stack whose values run one way from bottom to top. For next greater values they never rise: each sits on one at least as large.

position, not value

The stack holds indices: nums[j] gives the value, j says which answer to fill in, and i − j how long it waited.

amortised cost

The cost per step averaged over the whole run. One new value can pop many, but every pop uses up a push made earlier.

Take seven days of temperatures: 31, 28, 25, 29, 27, 34 and 30. The visualiser walks along them once, with a stack lane under the array, bottom on the left. Each new value is compared with the top: if the top is smaller, the new value is its answer and the top is popped; if not, popping stops and the new value is pushed to wait.

Two facts make this work. A value is pushed only after it has popped everything smaller than it, so it always lands on something at least as large: the values on the stack never rise from bottom to top. And so the first top that is not smaller ends the loop, because everything under it is at least as large again.

The stack lane draws values, but the algorithm keeps positions, as its narration says: “Compare 29 with the top of the stack, 25 (from position 2).”

Now count. Each comparison pops the top or stops the loop, so the 10 comparisons here are 5 pops and 5 stops.

Now 8, 3, 5, 5, 2, 7, 9 and 4. Before each comparison, predict whether the new value pops the top or stops. Watch what happens when 5 meets 5, and how far down the stack 7 gets.

Here is the same loop in code. answer starts as −1 everywhere, so a position never popped keeps it, and stack holds positions: nums[stack[-1]] is the value on top. It runs on 6, 2, 4, 1, 7 and 3.

def next_greater(nums):
    answer = [-1] * len(nums)
    stack = []
    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            j = stack.pop()
            answer[j] = nums[i]
        stack.append(i)
    return answer

result = next_greater([6, 2, 4, 1, 7, 3])
print(*result)

Popping j at position i writes answer[j], and i − j is how long j waited, which is all Days Until a Warmer Day asks for. Bare values couldn't say which cell to fill in, how long it waited, or, when a value repeats, which copy had been beaten.

The comparison is strict: a value pops the top only if it is greater. In the challenge, the second 5 stopped at the first and waited on top of it, and 7 later popped both.

One new value can pop a great deal. Here 19 falling values wait until 99 arrives.

The same loop answers a family of questions; only the comparison, the direction or when you read the stack changes.

• Next smaller value. Pop while the top is larger than the new value, so the stack rises from bottom to top.
• Previous greater value. Pop every value not larger than the new one (≤ this time); the top left behind, if any, is the nearest larger value to its left. Read it before the push.
• A circular list, where the first value follows the last. Go round twice, reading nums[i mod n] and pushing only on the first lap, so values still waiting meet the ones before them. Still O(n).
• The largest rectangle under a bar chart. A rectangle as tall as a bar stretches to the nearest lower bar on each side, so keep a stack of rising heights. A lower bar arriving is where each taller bar it pops stops on the right, the bar under a popped one on the stack is where it stops on the left, and a last bar of height 0 pops the rest. In 2, 4, 5, 3, 1, 3, the 1 at position 4 pops the 3 at position 3, whose rectangle runs back to just after the 2 at position 0: 3 × 3 = 9, the largest.

• Scanning right from every value is O(n²). A monotonic stack holds the positions still waiting for a larger value, whose values never rise from bottom to top. Each new value pops every smaller one, as their answer, then is pushed.
• Each position is pushed once and popped at most once: fewer than 2n comparisons, O(n) in all and O(1) amortised per value, even when one value pops the whole stack.
• Store positions, not values: they say which answer to fill in, and i − j is the distance. Pop on < for strictly greater, so equal values wait together. Positions left at the end have no answer.
• Flip the comparison for the next smaller value, pop on ≤ and read the top that is left for the previous greater, go round twice for a circular list, and keep rising bars for the largest rectangle under a bar chart.
• Next: practise with Days Until a Warmer Day, then the hard one, Largest Rectangle Under a Bar Chart. A falling stack of bars also solves Rainwater Between Bars, though two pointers do it in O(1) memory. To try your own values, open the monotonic stack visualiser.