LESSON 9 · PATTERN GUIDE

Monotonic Stack

Keep a stack in increasing or decreasing order to find the next greater or smaller item efficiently.

FIRST, LEARN THE PATTERNWhen a new value resolves older unresolved values, pop them. Each item enters and leaves the stack at most once.

The question asks for the next warmer day, next greater element, histogram rectangle, or nearest smaller boundary.

How to approach it

Scan once, popping while the current value resolves the stack top; push the current index to preserve distance information.

Watch out for

Choose strictly greater versus greater-or-equal behavior deliberately, especially when equal values appear.

A CLOSER EXPLANATION

The stack holds items whose answer is not known yet, in an order that makes the next value useful. When a new value is greater (or smaller), it resolves one or more waiting indices. Because an index is pushed once and popped once, the whole pass is linear even though there is a loop inside it.

NOW YOU TRY

Practice question

For each value, find the next greater value to its right in [2, 1, 3, 2, 4].

EXAMPLEvalues = [2, 1, 3, 2, 4]Give your answer before revealing the explanation.

Show a hint

Keep indices of values that have not yet seen a greater value.

Show an answer

[3, 3, 4, 4, -1]

CONNECT IT TO REAL LIFE

Monotonic Stack at work

For daily temperatures [18, 20, 17, 22], how many days must you wait after each day for a warmer temperature?

Show one possible approach

[1, 2, 1, 0]. The next warmer temperatures are 20, 22, 22, and none. A decreasing stack keeps days still waiting for a warmer reading.

Practice next

Use these problem IDs to find additional practice for this pattern:

7394965038485901