Monotonic Stack and Deque: Next Greater Element in O(n)

The brute force for 'find the next greater element for every element in an array' is O(n²): for each element, scan right until you find something larger. Most candidates reaching for this problem at a FAANG interview write exactly that — and then get asked to optimize it. The O(n) solution uses a monotonic stack, and the key insight is deceptively simple: each element is pushed and popped at most once, giving O(n) total operations across all n iterations of the outer loop.

The mechanism: maintain a stack of 'pending' elements — elements that have not yet found their next greater element. When you encounter a new element num, if it is larger than the top of the stack, then num is the next greater element for the stack top. Pop it, record the answer, and repeat while the new element is still larger than the current top. Then push the new element as a new pending candidate. Elements that remain on the stack after the full traversal have no next greater element — their answer is -1.

This pattern generalizes to six closely related problem types: next greater, next smaller, previous greater, previous smaller (by reversing traversal or reversing the comparison), and two range problems — largest rectangle in histogram and sliding window maximum — that require the same stack/deque discipline. Recognizing that these six problems all reduce to the same core operation is what separates candidates who internalize the pattern from those who memorize solutions.