0

Monotonic stack

Structuresused in ~70% of apps

The one pattern in this tier that does not look like anything you have seen. It answers "what is the next bigger thing to my right" for every position at once, in a single pass, and the first time you meet it, it looks like magic.

Core idea. Keep a stack whose values only ever increase (or only ever decrease) from bottom to top. Anything that would break that order gets popped off, and the moment a value is popped, the item that pushed it out <em>is</em> its answer.
Playground, this isn't a screenshot
next greater element, [2, 1, 4, 3]
2stack [2]nothing to pop. Push 2
1stack [2, 1]1 < 2, still decreasing. Push
4stack [4]1 → 42 → 44 beats both. Each gets its answer
3stack [4, 3]3 < 4. Push, still waiting
, stack []4 → none3 → noneend: whatever remains has no answer

The stack always reads decreasing from bottom to top. The moment that would break, somebody gets their answer.

↑ play a little first, then dig in