Back to Study Material Data Structures and Algorithms

Monotonic Stack

A monotonic stack is a stack that maintains its elements in a strictly increasing or strictly decreasing order from bottom to top at all times. This invari...

Monotonic Stack

What Is a Monotonic Stack and When to Use It

A monotonic stack is a stack that maintains its elements in a strictly increasing or strictly decreasing order from bottom to top at all times. This invariant is enforced during the push operation: before pushing a new element, all elements that would violate the ordering are popped. The popping step is not just cleanup; it is the core of the algorithm, because each element is popped exactly when a condition involving it and the new element is satisfied.

There are two variants. A monotonic increasing stack keeps elements in increasing order from bottom to top, meaning the bottom holds the smallest and the top holds the largest seen so far. When a new element is smaller than the top, elements are popped until the stack is empty or the top is smaller than the new element. A monotonic decreasing stack keeps elements in decreasing order, so elements are popped when the new element is larger.

The key insight is that each element is pushed and popped at most once. Even though the inner while loop pops elements, the total number of push and pop operations across the entire algorithm is O(n). This makes monotonic stack solutions O(n) time despite having a nested loop structure, a counterintuitive but important fact to communicate clearly in interviews.

Monotonic stacks solve a family of problems asking for the next greater element, next smaller element, previous greater element, or previous smaller element for each index in an array. These problems appear frequently in computational geometry, stock price analysis, and histogram area calculations.

The typical code pattern for a monotonic decreasing stack (used to find next greater elements) is: for each element, while the stack is not empty and the current element is greater than the element at the stack's top, pop and record the answer for the popped element as the current element; then push the current element's index. After the loop, elements remaining on the stack have no next greater element.

Worked example: array [2, 1, 5, 3, 4]. Use a monotonic decreasing stack storing indices. Index 0 (value 2): push 0. Index 1 (value 1): 1 < 2, push 1. Index 2 (value 5): 5 > 1, pop index 1, next greater for 1 is 5; 5 > 2, pop index 0, next greater for 2 is 5; push 2. Index 3 (value 3): push 3. Index 4 (value 4): 4 > 3, pop index 3, next greater for 3 is 4; push 4. Remaining indices 2 and 4 have no next greater element.

Interview tip: when you identify a next greater or next smaller element pattern in a problem, state explicitly that a monotonic stack will give O(n) time versus O(n squared) for a brute-force nested loop. This demonstrates you know the efficient approach before writing a single line.

Largest Rectangle in Histogram Using Monotonic Stack

The largest rectangle in a histogram is a classic hard problem that illustrates the power of the monotonic stack technique. Given an array of non-negative integers representing bar heights in a histogram where each bar has width one, find the area of the largest rectangle that fits entirely within the histogram.

The key observation is that for each bar, the largest rectangle that uses that bar as the shortest bar extends leftward to the first bar shorter than it and rightward to the first bar shorter than it. The width of that rectangle is the distance between those two boundaries minus one, and the height is the bar's own height.

A monotonic increasing stack (storing indices, not values) efficiently computes these boundaries in one pass. Scan left to right. Maintain a stack where all bars from bottom to top are increasing in height. When a bar shorter than the top of the stack is encountered, bars are popped. Each popped bar is the shortest bar in a rectangle: the right boundary is the current index, and the left boundary is the new top of the stack (or minus one if the stack is empty). The area is height times (right minus left minus one). After scanning all bars, pop remaining bars from the stack using the total length as the right boundary.

Time complexity is O(n) because each bar is pushed and popped at most once. Space complexity is O(n) for the stack. This is optimal since any algorithm must read all n bars.

An alternative approach adds sentinel bars of height zero at both ends of the array to simplify boundary handling, eliminating the need to handle the empty-stack case separately during the main loop.

Worked example: heights [2, 1, 5, 6, 2, 3]. After processing, the algorithm finds rectangles of area 10 (using heights 5 and 6 with width 2) and area 10 (height 2 spanning all six bars). The maximum is 10.

Interview tip: this problem is commonly paired with the maximal rectangle in a binary matrix problem, which reduces to running the histogram algorithm on each row. Mention this connection proactively to demonstrate breadth of knowledge beyond the single problem at hand.

Daily Temperatures and Stock Span with Monotonic Stacks

Two popular interview problems, daily temperatures and stock span, both reduce cleanly to monotonic stack solutions once the underlying pattern is recognized. Practicing both builds pattern recognition for this entire family of problems.

The daily temperatures problem gives an array of daily temperatures and asks for an output array where each position contains the number of days until a warmer temperature occurs. If no warmer day follows, the answer for that day is zero. This is precisely the next greater element problem applied to temperature data.

Use a monotonic decreasing stack storing indices. For each day, while the stack is not empty and the current temperature is higher than the temperature at the index on top of the stack, pop the top index and set its answer to the current day minus the popped index. Then push the current day's index. Days that remain on the stack after the full scan receive an answer of zero. Time complexity O(n), space complexity O(n).

The stock span problem asks for the number of consecutive days up to and including the current day where the stock price was less than or equal to the current price. This is equivalent to finding the previous greater element. Use a monotonic decreasing stack storing indices. For each day, pop all indices whose price is less than or equal to the current price. The span is the current index minus the new top of the stack (or the current index plus one if the stack is empty). Then push the current index.

Both problems share the same underlying structure: maintain a monotonic stack and process events when the monotonic property is about to be violated. The difference lies only in what information you store (values versus indices) and what computation you perform on each pop.

Worked example for stock span: prices [100, 80, 60, 70, 60, 75, 85]. Spans are [1, 1, 1, 2, 1, 4, 6]. At price 75 on day 5, the stack pops 60 (span extends), 70 (span extends), 60 (span extends), all less than 75, leaving 80 on the stack. Span is 5 minus index of 80, which is 1, giving 4.

Interview tip: after solving a monotonic stack problem correctly, mention that the same stack can often simultaneously compute both the next greater and previous greater elements in a single pass, which halves the constant factor in problems requiring both.