Monotonic Stack: Next Greater Element
Medium+85 XPKeep a stack that stays sorted in one direction to find each number's next-greater element in a single O(n) pass.
No visualization loaded.
Watch
—
Press Run to begin.
Imagine a line of numbers and you want, for each one, the FIRST number to its right that is bigger (its 'next-greater'). The slow way is to stand on each number and look rightward until you find a bigger one — that re-checks the same numbers over and over. The fast way uses a special stack: a 'monotonic' stack, which just means the numbers in it always stay in order one way (here, biggest at the bottom, getting smaller as you go up). As you walk left to right, whenever the new number is bigger than the one sitting on top of the stack, that top number has just met its next-greater — so you pop it off and write down the answer. Each number is put on the stack once and taken off at most once, so the whole thing is fast.
▸What does 'monotonic' mean?
Monotonic just means 'always moving in one direction — never flip-flopping.' A monotonic stack is a stack whose values stay sorted one way the whole time. Here we keep it DECREASING from bottom to top: the bottom holds the biggest waiting number and each one above is smaller. We never let a bigger number sit on top of a smaller one — if a new value would break that rule, we pop until it fits.
▸Why does keeping the stack decreasing let each number be touched only once?
A number goes ONTO the stack exactly once (when we reach it). It comes OFF exactly once — the moment we meet a bigger number to its right, which is its next-greater. After that it's done forever; we never look at it again. So across the whole scan there are at most n pushes and n pops. n + n is still proportional to n, which is why it's O(n) total even though there's a loop inside the loop.
▸Why is the brute-force way slow?
The slow way stands on each number and scans every number to its right until it finds a bigger one. In the worst case (like a list that keeps climbing), every number scans almost the whole rest of the list — that's about n × n comparisons, which is O(n²). It keeps re-reading the same numbers it already looked at. The stack remembers the unresolved numbers for us, so we never rescan.
▸What real problems are just 'next greater element' in disguise?
Lots! 'Daily temperatures' (how many days until a warmer day) is next-greater on dates. 'Stock span' (how many days a stock price stayed below today's) is the mirror image — next-greater looking left. The 'largest rectangle in a histogram' uses the same monotonic-stack trick to find, for each bar, how far it can stretch. Once you spot 'for each item, find the nearest bigger/smaller one,' reach for a monotonic stack.
How the work grows
O(n) is fair — grows in step with the data. We make one left-to-right pass. Each index is pushed onto the stack once and popped at most once, so the total push+pop work is at most 2n — that's O(n), not the O(n²) of re-scanning the right side for every element. The extra memory is the stack, which in the worst case (a decreasing list) holds all n indices.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.