Monotonic Stack Explained: Next Greater Element and the Problems It Unlocks

Most coding interview candidates write nested loops for range queries because scanning left and right feels natural before it feels slow. That $O(n^2)$ habit destroys performance on arrays with thousands of elements when the interviewer expects $O(n)$. A monotonic stack solves this by maintaining a strict ascending or descending order inside the data structure, popping elements the moment they violate that rule.

The Core Mechanism

Take the array [2, 1, 4, 3]. If you want to find the next greater element for every index, a brute force approach checks every subsequent number until it finds a larger one. For an array of size $10^5$, that takes roughly $10^{10}$ operations and times out immediately.

A monotonic decreasing stack stores indices instead of values, keeping the heights at those indices in descending order from bottom to top. When you encounter 4, it is greater than 1 at index 1 and 2 at index 0. The stack pops both, records 4 as their next greater element, and pushes 4. Every element enters the stack once and leaves the stack once, which collapses the time complexity to $O(n)$ despite the loop inside a loop.

Spotting the Pattern

Interview problems that require a monotonic stack always revolve around finding the nearest element to the left or right that is greater or smaller than the current element. If a question asks for spans, bounds, or temperatures until a warmer day, look at the constraints. When $n$ is up to $10^5$, $O(n^2)$ is forbidden, which forces a stack-based linear scan.

Daily Temperatures asks for the number of days you must wait until a warmer temperature appears, given an array like [73, 74, 75, 71, 69, 72, 76, 73]. A monotonic decreasing stack of indices holds days whose temperatures have not yet found a warmer successor. When index 5 with temperature 72 arrives, it pops index 4 (69) and index 3 (71) because 72 is warmer than both, calculates the day differences, and pushes itself onto the stack.

Stock Span measures the consecutive days before the current day where the price was less than or equal to today's price, given [100, 80, 60, 70, 60, 75, 85]. A monotonic decreasing stack stores prices and their spans, accumulating the span counts of popped elements before adding the current day to the stack.

The Histogram Exception

Largest Rectangle in Histogram uses a monotonic increasing stack because you need to find the first bar shorter than the current bar to establish the left and right boundaries of a rectangle. Given heights [2, 1, 5, 6, 2, 3], the stack keeps indices of increasing heights. When a shorter bar appears, it triggers the calculation of rectangle areas for all taller bars trapped to its left, using the distance between indices as the width. The stack enforces order in reverse, finding the drop-off points that bound the maximum possible area.

If the problem asks for the maximum area of a rectangle in a matrix of ones and zeros, convert each row into a histogram and run this exact stack algorithm row by row.

Open DSA Tracker and code the Next Greater Element problem from scratch without looking at the solution template.