Monotonic Stack is a pattern that shows up in LeetCode problems where you need to find the next greater or smaller element in an array.

With this pattern, you can reduce the time complexity of many array problems from O(n²) down to O(n).

This chapter covers:

A Monotonic Stack is a stack whose elements stay in either increasing or decreasing order from bottom to top.

The stack maintains a monotonic order: at any moment, the values stored (from bottom to top) form an increasing or decreasing sequence. Before pushing the current element, pop all stack-top elements that violate the invariant.

In a Monotonic Increasing Stack, the values from bottom to top form an increasing sequence. Before pushing a new element, pop any top elements that violate the order.

In a Monotonic Decreasing Stack, the values from bottom to top form a decreasing sequence. Before pushing a new element, pop any top elements that violate the order.

The chapter's example uses a strict comparison (>), which pops only elements strictly smaller than the current one and leaves equal elements in place. The choice between strict (>) and non-strict (>=) depends on the problem: Daily Temperatures uses strict comparison, while some histogram variants require non-strict.

In most problems, store the indices of the numbers in the stack rather than the actual values.

This gives you more flexibility when accessing values from the array by index.

Consider an example problem: Next Greater Element.

The task is to find the next greater element for each number in an array.

The "next greater element" is the first number to the right that is larger than the current number.

Consider the array:

We want to find the next greater element for each number:

A brute force solution would involve a nested loop comparing each element with elements to its right until a greater element is found.

But this would take O(n²) time in the worst case.

Using a monotonic stack, we can bring the time complexity down to O(n).

The approach works as follows:

We use ArrayDeque instead of java.util.Stack. java.util.Stack is synchronized and considered legacy; ArrayDeque is the recommended stack implementation in modern Java.

Walk through an example.

The array is [2, 1, 5, 6, 2, 3].

We maintain the following:

Go through the array step by step:

After processing all the numbers, the result array is [5, 5, 6, -1, 3, -1].

The algorithm finds the next greater element for each index in O(n) time.

The presence of a while loop inside a for loop usually suggests O(n²) behavior, but this case is different. The total work is bounded by counting how many times each index can be pushed and popped.

Each index is pushed onto the stack exactly once, when the outer loop reaches it. Each index is popped at most once, because once it leaves the stack it never returns. Across the entire run of the outer loop, the total number of push operations is n, and the total number of pop operations is at most n.

The inner while loop only runs when it can pop something. Its cost across the full outer loop sums to at most n, not n per outer iteration. The combined work is n pushes plus at most n pops plus n outer iterations, which is O(n) in total. This counting argument is the standard amortized analysis used for monotonic stack problems.

The next greater element template covered above is one of four canonical variants. The same stack idea handles all of them with small tweaks to the comparison and the moment the answer is recorded.

The two "right" variants record the answer at the moment of popping: the element that triggers the pop is the next greater (or smaller) for the popped index. The two "left" variants record the answer from the stack top before pushing the current index, since whatever survives the pop chain on top of the stack is the previous greater (or smaller).

Below is the Previous Smaller Element template in all eight languages, mirroring the structure of the Next Greater template above:

The next-greater template above demonstrates the right-side pattern: the answer is written when an index is popped. The previous-smaller template demonstrates the left-side pattern: the answer is read from the surviving top of the stack right before the current index is pushed. Once both patterns are familiar, the other two variants are obtained by flipping the comparison operator.

The choice between strict (>) and non-strict (>=) inside the while condition decides what happens to equal elements. With strict comparison, equal elements stay on the stack and become part of the answer chain. With non-strict comparison, equal elements pop each other and are merged.

The right choice depends on the problem:

The guideline is to decide based on whether equal elements should be treated as still satisfying the condition or no longer satisfying it. If two equal values should both count as valid answers, use strict comparison so the older one survives. If they should be collapsed into a single representative, use non-strict comparison so the older one is popped.

For problems like Largest Rectangle in Histogram or Sum of Subarray Minimums, every remaining element on the stack must still be processed when the outer loop ends. The standard trick is to append a sentinel value to the input that forces every remaining element to pop.

For histogram problems, append a 0 (smaller than any real bar height). For next-greater problems, append INT_MAX (larger than any real value). The sentinel triggers the pop chain one final time, draining the stack inside the main loop without a separate post-loop:

Without the sentinel, the loop body has to be duplicated after the loop ends to drain whatever remains on the stack. The sentinel removes that duplication and keeps the main logic in one place.

A monotonic stack is LIFO. It works when the only boundary that matters is the most recent one, which covers next/previous greater/smaller problems.

A monotonic deque is a double-ended queue. It is needed when elements must also be evicted from the front, typically because of a sliding window constraint. The canonical example is Sliding Window Maximum (LC 239): the deque holds candidate indices in decreasing order of value, the front of the deque is the current window's maximum, and elements are evicted from the front when their index falls outside the window.

The mechanics of the back are identical between the two. Both structures pop from the back to maintain the monotonic invariant when a new element arrives. The only added rule for the deque is the front-side eviction driven by window bounds. A monotonic stack is what a monotonic deque becomes when no such eviction is ever needed.

The same monotonic stack template, with small variations on comparison and what to record, solves a recurring family of problems:

Storing indices on the stack rather than values keeps positional information available. Many problems need the distance between two positions, not just the comparison result. Daily Temperatures asks "how many days until warmer", which requires computing j - i when an element pops. Largest Rectangle needs both the boundary index (to compute width) and the bar height (to compute area).

As a default, store indices and read values through nums[stack.peek()] when comparing. The index gives access to both the position and the value; the reverse is not true.