Monotonic stack
Scenario
You're looking at a line of people and want to find the next person taller than you. You could ask everyone in line one by one.
Is there a way to find the next taller person for everyone in just a single pass?
Why it exists
Problem: Resolving relationships between sequentially processed elements (like finding the next greater element) normally requires O(n^2) nested scanning.
Naive approach: For every element, scanning all subsequent elements in a nested loop to find the next greater/smaller match, resulting in O(n^2) time.
Better idea: Maintain elements in a strictly ordered sequence (increasing or decreasing). Incoming elements forcefully evict elements that violate the order. The moment an element is evicted, we've found its answer. This yields O(n) amortized time.
Mental model
A localized memory buffer for elements 'waiting' for a specific condition. A massive element comes in and bulldozes all the smaller elements waiting in line.
A monotonic stack enforces order via a forceful eviction policy during the push operation. If the stack is strictly decreasing, smaller elements sit on top of larger ones. When a large element arrives, it shatters the invariant, forcing all smaller elements to pop. The popped elements acknowledge the incoming element as their 'next greater' match. We typically store array *indices* instead of values to calculate distances and update result arrays.
Repeated decision: Does the incoming element violate the monotonic order? If so, pop the top of the stack and resolve its answer.
Explanation
The monotonic stack is one of the most powerful and feared interview patterns. It fundamentally solves the 'next greater' or 'next smaller' query over an entire array in O(n) amortized time.
The beauty of this structure is that the *destruction* of the invariant provides the answer. Elements wait peacefully on the stack in order. The moment a contradictory element arrives, it triggers a cascade of pops. Each pop is an element realizing that its wait is over: the incoming element is exactly what it was waiting for.
Here is the vital direction rule to memorize: Keep the stack DECREASING to find the next GREATER element (pop when a bigger element arrives); keep it INCREASING to find the next SMALLER element / to bound areas like histogram bars (pop when a smaller element arrives). Understanding this choice is the key to mastering the pattern. While the nested while loop looks like O(n^2), amortized analysis proves it is O(n) overall because every element is pushed exactly once and popped at most once.
The same eviction machinery solves area problems like the largest rectangle in a histogram. Keep an INCREASING stack of bar indices; when a shorter bar arrives it evicts taller bars, and each evicted bar's rectangle is bounded on the right by the current index and on the left by the NEW stack top after popping — so its width is `current_index - stack.top() - 1`. Append a single sentinel bar of height 0 at the end to force every remaining bar to flush and be measured.
Key points
- Invariant: The stack elements remain strictly increasing or decreasing from bottom to top.
- Complexity: O(n) amortized time, as each element is pushed and popped at most once.
- Recognition cue: Finding the next greater/smaller element, or computing bounds like in histogram areas.
Pattern: Monotonic Eviction
Recognition cues:
- Next greater/smaller element
- Finding the nearest element that satisfies a magnitude condition
- Histogram/Area problems
Failure signals
- The problem doesn't involve relative ordering or range queries.
- Looking for absolute max/min of the entire array (use a standard variable).
Engineering examples
Financial Span Calculations
Stock market span problem
Computes consecutive previous days a stock was lower by ejecting all previous days with lower prices, allowing instant calculation to the nearest prior peak.
Geometric Area Problems
Largest rectangle in a histogram
Shorter bars trigger evictions of taller bars, allowing the calculation of locally bounded areas efficiently.
Common mistakes
- Believing it is O(n^2) time complexity: Because there is a while loop inside a for loop, developers incorrectly assume O(n^2). Amortized analysis proves O(n) because each element is pushed and popped at most once.
- Storing values instead of indices: Storing actual integer values loses spatial metadata. Storing indices allows resolving distance calculations and placing answers in a pre-allocated result array.
Recall questions
- What is the amortized time complexity of traversing an array with a monotonic stack, and why?
- To find the 'next greater element', should you use a strictly increasing or strictly decreasing monotonic stack?
- Why is it usually better to push array indices onto the monotonic stack rather than values?
Questions & answers
Find the maximum area of a rectangle in a histogram.
Use an increasing monotonic stack. When a shorter bar arrives, pop taller bars, calculating their bounded area using the current index and the new top of stack index. To compute the width, use the formula `current_index - stack.top() - 1` using the NEW top after popping as the left boundary. Use a sentinel trick: append a 0-height bar at the end of the array to flush any remaining elements from the stack.
Approach: Identify that shorter bars act as rigid boundary limits for taller bars.
Calculate the stock span for each day.
Use a decreasing stack of indices. When a higher price arrives, pop lower prices. The span is the current index minus the index now at the top of the stack.
Approach: Evicting lower prices resolves the 'consecutive previous days' constraint.
Continue learning
Previous: Stack fundamentals
Next: Next greater element
Related: Next greater element