Monotonic Stack: Next Greater/Smaller

A monotonic stack is a stack whose items stay in sorted order, increasing or decreasing from bottom to top. It answers "for each element, what is the next (or previous) element that is greater / smaller / satisfies some condition?" in $O(n)$ instead of the $O(n^2)$ nested loop. The other monotonic stack notes in this category build on the loop you'll learn here.

The idea#

Scan left to right. The stack holds the elements that are still waiting for their answer. When a new element arrives, every waiting element it beats has found its answer: pop it and record the result. Then push the new element; it waits too.

Why is it safe to pop? You only pop elements that are no longer useful. Once x has answered an element y, nothing to the right will ever need y again, because x is closer and at least as good. What's left in the stack is automatically sorted: for next greater, the values never increase from bottom to top, since anything smaller than a newer item would have been popped.

Each index is pushed once and popped at most once, so the total work is $O(n)$ , even with the inner while.

How to spot it#

The question asks, for every element, about the first element after it that beats it. Look for these signals.

"Next greater element", "next smaller", "how many days until a warmer temperature".
"For each element, the first element to its right (or left) that ...".
A running stream where each new item settles older items (stock prices, cars catching up).
The brute force is "for each i, scan right until ...", which is $O(n^2)$ .

Template#

Store indices, not values: an index gives you both the value (nums[i]) and the distance (j - i).

ans = default for every index        # e.g. -1
stack = empty                        # indices still waiting
for i in range(len(nums)):
    x = nums[i]
    while stack and x beats nums[top]:
        j = pop from stack
        ans[j] = x                   # or the distance i - j
    push i                           # i waits for its own answer
return ans

The same loop handles a circular array with one change: loop 2n times and use i % n. The second lap lets elements near the end find answers at the start. It only answers; it never pushes.

Here is the plain (non-circular) loop on a small input. The trace finds the next greater element in [2, 1, 2, 4, 3], with the stack shown as values:

`i`	`x`	Popped (gets answer `x`)	Stack after
0	2		`[2]`
1	1		`[2, 1]`
2	2	1	`[2, 2]`
3	4	2, 2	`[4]`
4	3		`[4, 3]`

The 4 and 3 never get popped, so they keep the default -1.

Choosing the comparison#

The trace used "next greater", but the same template answers four questions. Only the pop condition and the stack's order change:

You want	Pop while the top is	Stack order (bottom to top)
Next greater	`< x`	non-increasing
Next greater or equal	`<= x`	strictly decreasing
Next smaller	`> x`	non-decreasing
Next smaller or equal	`>= x`	strictly increasing

For the previous greater or smaller, use the same loop: after popping, the element left on top (if any) is the answer for x. Or scan from right to left.

Pitfalls#

These slips give wrong answers on duplicates and edges.

Storing values when you need positions. Store indices (or (value, index) pairs) whenever the answer is a distance or the array may have duplicates.
Wrong strictness. "Next greater" pops on <; "greater or equal" pops on <=. Check the wording for "or equal".
Circular arrays. A single pass leaves answers on the table. For "circular", think % n and loop 2n times.
Forgetting the defaults. Elements left in the stack at the end have no answer; initialize ans with the problem's default (-1, 0).

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first three.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Next Greater Element I

The queries are values from a second array. Run the template over nums2 and store each popped value's answer in a dict. Then look up each query, with -1 as the default.

Hint: Final Prices With a Special Discount in a Shop

The discount is the next price less than or equal to the current one. That is "next smaller or equal", so pop while the top's price is >= x.

Hint: Daily Temperatures

You want a distance, not a value. Record i - popped_index for each popped day, and leave 0 for days that never get popped.

Hint: Next Greater Element II

The array is circular. Loop 2n times with x = nums[i % n], and push only while i < n.

Hint: Car Fleet

Sort the cars by position, closest to the target first, and compute each arrival time (target - pos) / speed. If a car behind arrives no later than the fleet ahead (its time <= the top), it joins that fleet, so don't push it. The answer is the stack's size.

Key takeaways#

The stack holds elements still waiting for their answer.
A new element pops (and answers) everything it beats, then waits itself.
Each index is pushed and popped once, so it's $O(n)$ .
Pop on < for next greater, > for next smaller; add = for "or equal".
Circular array: loop 2n and use % n.

Core idea#

The stack holds elements still waiting for their answer. A new element pops and answers every element it beats, then waits itself.

Key points#

Each index is pushed once and popped at most once, so the scan is $O(n)$ , not $O(n^2)$ .
A popped element is no longer useful. The new element is closer and at least as good.
Store indices. An index gives the value and the distance j - i.
Previous greater or smaller: after popping, the top is the answer for x. Or scan right to left.
Circular array: loop 2n times and use i % n. The second lap only answers.
Spot it: "next greater", "days until a warmer temperature", "first element to the right that ...".

Choosing the comparison#

You want	Pop while the top is	Stack order (bottom to top)
Next greater	`< x`	non-increasing
Next greater or equal	`<= x`	strictly decreasing
Next smaller	`> x`	non-decreasing
Next smaller or equal	`>= x`	strictly increasing

Template#

ans = default for every index      # e.g. -1
stack = empty                      # indices still waiting
for i in range(len(nums)):         # circular: 2n laps, i % n
    x = nums[i]
    while stack and x beats nums[top]:
        ans[pop from stack] = x    # or the distance
    push i                         # second lap never pushes
return ans

Variants#

Daily Temperatures: record i - popped_index.
Next Greater Element I: run over nums2, store answers in a dict, look up queries.
Car Fleet: sort by position, closest to the target first. Push arrival times. A car with time <= the top joins that fleet. The answer is the stack size.

Pitfalls#

Storing values when the answer is a distance or duplicates exist.
Wrong strictness. "Greater or equal" pops on <=; "smaller or equal" pops on >=.
One pass on a circular array. Loop 2n times.
Wrong defaults. Elements left on the stack keep the default (-1, 0).

Say it in an interview#

"The stack holds elements still waiting for their answer."
"Each index is pushed and popped once, so it's O(n) despite the inner while."