Monotonic Stack Patterns

Mastering the monotonic stack is a rite of passage for any serious programmer tackling algorithm interviews. It transforms problems that appear to require nested loops—and $O(n^2)$ time complexity—into elegant, single-pass solutions that run in $O(n)$ time. This powerful pattern is the key to efficiently solving a suite of classic challenges, from finding the next greater element in an array to calculating how much rainwater a cityscape can trap.

What is a Monotonic Stack?

A monotonic stack is a stack data structure where its elements are kept in strictly increasing or strictly decreasing order from the bottom to the top. The "monotonic" property is an invariant—a rule that must always be true. When you try to push a new element onto the stack, you must first pop elements from the top until pushing the new element no longer violates the sorted order. This process of maintaining the invariant through strategic popping is the engine of its efficiency.

The core idea is to use the stack to remember previous elements in a processed order, allowing you to resolve relationships (like "next greater" or "previous smaller") in a single pass. Instead of comparing every element to every other element, you defer computations until a later element provides the necessary information, at which point you can resolve all waiting elements at once.

The Invariant and the Popping Mechanism

The algorithm's power comes from its strict enforcement of the monotonic property. Consider a monotonically decreasing stack (elements decrease from bottom to top). When you process a new element, you compare it to the top of the stack. If the new element is greater than or equal to the top, it would break the decreasing order. Therefore, you pop the top element. For the popped element, the new element you are trying to push is its next greater element (or equal element). You repeat this pop-and-compare process until the top of the stack is greater than the new element (or the stack is empty), at which point you push the new element onto the stack, preserving the invariant.

This popping step is where the computation happens. Each pop resolves a pending query: "What is the next greater element for this index?" By the time you finish processing the array, any elements left in the stack are those for which no qualifying element (like a next greater element) exists, and you can assign them a default value like -1.

Increasing vs. Decreasing Stacks

Choosing the correct monotonic direction is critical and depends on the problem's relationship you need to find.

• A Monotonically Decreasing Stack is used when you need to find the next greater element (NGE). As described, you pop when you encounter a new element that is greater than the stack's top. The stack holds elements in decreasing order, waiting for their "greater" match to appear.
• A Monotonically Increasing Stack is used when you need to find the next smaller element. Here, you pop from the stack when the new element is smaller than the stack's top. The stack holds elements in increasing order, waiting for their "smaller" match.

You can also process arrays from left-to-right or right-to-left, and combine stack direction with processing order to find "previous greater" or "previous smaller" elements. The fundamental logic remains the same: maintain the sorted invariant by popping, and perform your core calculation during the pop.

Key Application: Next Greater Element

The classic problem: Given an array of integers, return an array where each element is replaced by the next greater element to its right. If none exists, use -1.

Solution with a Decreasing Stack: We process the array from left to right, maintaining a decreasing stack of indices. For each new element nums[i]:

1. While the stack is not empty and nums[i] > nums[stack.top()]:

• The new element nums[i] is the next greater element for the index at the stack's top.
• Record this: result[stack.top()] = nums[i].
• Pop the top index.

1. Push the current index i onto the stack.

After the loop, any indices remaining in the stack have no NGE, so their result is set to -1. This single pass yields an $O(n)$ solution.

Example for array [2, 1, 2, 4, 3]:

• Process 2: Stack is empty, push index 0. Stack: [0]
• Process 1: 1 is not > 2, push index 1. Stack: [0, 1]
• Process 2: 2 > nums[1]=1. Pop 1, set result[1]=2. 2 is not > nums[0]=2. Push index 2. Stack: [0, 2]
• Process 4: 4 > nums[2]=2. Pop 2, set result[2]=4. 4 > nums[0]=2. Pop 0, set result[0]=4. Push index 3. Stack: [3]
• Process 3: 3 is not > 4, push index 4. Stack: [3, 4]
• End: Set result[3] = -1, result[4] = -1.
• Final Result: [4, 2, 4, -1, -1].

Key Application: Largest Rectangle in Histogram

This is a more advanced application. Given an array heights representing a histogram's bar heights, find the area of the largest rectangle.

Solution with an Increasing Stack: The insight is that a rectangle is limited by the first bar shorter than its current height on either side. We use a monotonically increasing stack of indices to find the previous smaller and next smaller element for each bar in one pass. The width of the rectangle with height heights[i] extends from the index after the previous smaller bar to the index before the next smaller bar.

Algorithm:

1. Initialize an increasing stack and process indices from 0 to n (treating index n as a bar of height 0 to force a final cleanup).
2. While the stack is not empty and heights[i] < heights[stack.top()]:

• The current index i is the next smaller element for the bar at h = heights[stack.top()]. Pop it.
• The previous smaller element for the popped bar is the new top of the stack (or -1 if empty).
• Calculate width: width = i - stack.top() - 1 (or i if stack is empty).
• Calculate area: area = h * width. Update the maximum area.

1. Push the current index i onto the stack.

This $O(n)$ algorithm elegantly finds the limiting boundaries for each bar as it is popped from the stack.

Common Pitfalls

1. Misidentifying Stack Order: The most frequent error is using an increasing stack to find the next greater element or vice-versa. Remember the rule: Decreasing Stack finds Next Greater. Increasing Stack finds Next Smaller. A mnemonic: "You need to go down to find up" (a decreasing stack finds a greater element).

1. Storing Values vs. Indices: For most array-based problems, you must store indices in the stack, not just values. Values alone are insufficient to calculate widths (as in the histogram problem) or to assign results to the correct position in an output array. The index gives you access to both the value and its positional context.

1. Incorrect Loop Termination and Cleanup: Problems like "Daily Temperatures" or "Next Greater Element" often leave elements in the stack with unresolved queries. You must remember to iterate through the remaining stack after your main loop and assign default values (like 0 or -1). Conversely, in the histogram problem, you must append a sentinel value (like a 0-height bar) to the end to ensure all bars are popped and processed.

1. Handling Duplicate Values: Decide whether your monotonic stack should be strictly increasing/decreasing or non-strict (allowing equals). For "next greater element," you typically use > (strict). For the histogram problem, you often use >= in the while condition to correctly handle duplicate heights and avoid overcounting widths. The choice depends on the problem's definition of "greater" or "smaller."

Summary

• A monotonic stack maintains elements in sorted order by popping elements that violate the invariant when pushing new ones. This popping action is where the primary computation occurs.
• Use a monotonically decreasing stack to find the next greater element. Use a monotonically increasing stack to find the next smaller element.
• The pattern delivers $O(n)$ time complexity for problems that naively require $O(n^2)$, by resolving element relationships in a single, clever pass.
• Key applications include solving the Next Greater Element, Daily Temperatures, Largest Rectangle in Histogram, and Trapping Rain Water problems.
• Avoid common mistakes by carefully choosing stack order (increasing vs. decreasing), storing indices instead of just values, and properly handling loop termination and duplicate values.