Monotonic stack & queue

The idea

Items wait on a stack until something bigger arrives

For each day's temperature, how many days until a warmer one? Checking forward from every day is O(n²). Instead, read the days in order and keep the days still waiting for an answer on a stack.

When a new day arrives, it is the answer for every waiting day that is colder. Those are all on top of the stack, because the stack never holds a warmer day above a colder one: pop them, record their answers, then push the new day to wait its turn. That ordering, always falling (or always rising) from bottom to top, makes it a monotonic stack.

The rule

Every item is pushed once and popped at most once, so a monotonic stack processes n items in O(n), however many pops happen on a single step.

Spotting it

"Next bigger", "previous smaller" and "maximum of every window"

The next greater (or smaller) element for every item

A stack that falls (or rises) from bottom to top

How many days until a warmer day; a stock's span

The same stack, storing positions

The largest rectangle under a bar chart

A rising stack: a bar is popped when a shorter one ends its rectangle

The maximum or minimum of every window of size k

A monotonic queue: the stack's trick, plus expiry at the front

Basic

Days until a warmer day

The stack holds the positions of days still waiting. Watch one warm day settle several waiting days at once.

Positions, not temperatures, go on the stack: the answer is a distance in days, and the temperature can always be looked up from the position.

Medium

The maximum of every window

A sliding window of size k moves along the list, and each position needs the window's maximum. A monotonic queue keeps the positions of the window's candidates, falling from front to back, so the front is always the maximum. Two things change from the stack:

a new item removes, from the back, every candidate that is no bigger than it: those are older and smaller, so they can never be a window's maximum again;
the item at the front is removed once the window has slid past its position.

Each position enters the queue once and leaves at most once, from one end or the other: O(n) for all the windows, instead of O(n × k) for scanning each window.

Hard

A rectangle ends when a shorter bar arrives

Each bar's best rectangle uses its full height and stretches left and right until a shorter bar blocks it. A rising stack of bars finds both ends: when a shorter bar arrives, every taller bar on top of the stack has just met its right end, and the bar now below it on the stack marks its left end: the rectangle starts just after that bar.

The template

The shape to reuse

1stack ← []
2for i from 0 to length of xs − 1
3 while stack is not empty and xs[top of stack] < xs[i]
4 j ← pop(stack)
5 -- xs[i] is the next greater element for position j
6 append i to stack

Flip < to > for the next smaller element. For the monotonic queue, add the expiry check at the front, popFront, before using the front as the answer.

Traps

Where monotonic-stack solutions go wrong

Storing values instead of positions

Most questions need a distance or a position; store positions and look values up.

`<` versus `≤` with equal values

Decide whether an equal item counts as "greater"; the wrong choice either pops too much or leaves stale items waiting.

Items left on the stack

When the loop ends, whatever is still waiting has no answer (0, −1 or the end of the list, as the problem says).

Forgetting expiry in the queue

A front position outside the window gives a maximum that isn't in the window.

Check yourself

3 questions

1. Temperatures 70, 68, 65, then 72. When 72 arrives, the stack holds the days of 70, 68 and 65. What happens?

2. A single step can pop many items. Why is the whole pass still O(n)?

3. For the maximum of every window, what does the monotonic queue add to the stack's trick?

Takeaways

Remember this

A monotonic stack keeps positions in falling (or rising) order; each new item pops and answers every smaller item waiting.
Every item is pushed once and popped at most once, so the whole pass is O(n).
A monotonic queue adds expiry at the front, which gives the maximum of every sliding window in O(n).

Practice

Now solve some yourself

Mixed with topics you have practiced 0 unlocked

3 more once you have practiced Greedy algorithms, Linked lists, Prefix sums. Play one of its examples to the end and solve one of its problems to unlock them.

Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.