Stack

AI Generated

LIFO. Reach for it whenever an element's answer depends on the most recent unresolved element before it.

• Monotonic stack — keep the stack sorted (increasing or decreasing). Pop while the incoming element breaks that order, and settle each popped element as it leaves. This is "next greater / next smaller element" in O(n), and it's what daily temperatures and largest histogram really are.
• Push indices, not values — you nearly always need a width or a day difference, not just the value.
• Matching and nesting — push the opener, pop on the closer.

Recursion is a stack too, so backtracking problems are the same tool with the call stack doing the pushing.