Advanced Pattern

What Is a Monotonic Stack?

A monotonic stack is a stack whose elements are always in sorted order. Either strictly increasing or strictly decreasing from bottom to top. This property is maintained by popping elements that violate the order before pushing new ones.

There are two variants:

• Monotonic decreasing stack: Elements from bottom to top are in decreasing order. Used to find the next greater element.
• Monotonic increasing stack: Elements from bottom to top are in increasing order. Used to find the next smaller element.

The key insight is that when a new element violates the monotonic property, you pop elements from the stack and process them. The new element is the answer for all the popped elements. Review basic stack operations

The Next Greater Element Pattern

Given an array, find the next greater element for each position. The next greater element is the first element to the right that is larger. If none exists, the answer is -1.

Example: For [2, 1, 2, 4, 3], the next greater elements are [4, 2, 4, -1, -1].

Step-by-step with a decreasing monotonic stack (store indices):

1. Index 0, value 2: Stack is empty. Push index 0. Stack: [0]
2. Index 1, value 1: 1 < 2. Push index 1. Stack: [0, 1]
3. Index 2, value 2: 2 > 1. Pop index 1. Answer for index 1 is 2 (value at index 2). 2 is not > 2, so stop. Push index 2. Stack: [0, 2]
4. Index 3, value 4: 4 > 2. Pop index 2. Answer for index 2 is 4. 4 > 2. Pop index 0. Answer for index 0 is 4. Stack empty. Push index 3. Stack: [3]
5. Index 4, value 3: 3 < 4. Push index 4. Stack: [3, 4]
6. End of array: Remaining indices (3, 4) have no next greater element. Answer: -1.

Finding Next Smaller Element

The mirror problem uses a monotonic increasing stack. For each element, find the first element to the right that is smaller.

For [4, 5, 2, 10, 8], the next smaller elements are [2, 2, -1, -1, -1].

Use the same algorithm but reverse the comparison: pop while the current element is smaller than the stack top instead of larger.

Largest Rectangle in Histogram

Given an array of histogram bar heights, find the area of the largest rectangle that can be formed. This classic problem uses a monotonic increasing stack to find, for each bar, how far it extends left and right while maintaining its height.

For heights [2, 1, 5, 6, 2, 3], the answer is 10 (the rectangle formed by bars at indices 2 and 3, with height 5 and width 2).

Algorithm: Maintain an increasing stack of indices. When a shorter bar is encountered, pop taller bars and calculate their area using the current index as the right boundary and the new stack top as the left boundary. Practice this and more interview problems

Daily Temperatures

Given daily temperatures, find how many days you must wait for a warmer temperature. If no warmer day exists, use 0.

For [73, 74, 75, 71, 69, 72, 76, 73], the answer is [1, 1, 4, 2, 1, 1, 0, 0].

Use a decreasing monotonic stack of indices. When you encounter a warmer day, pop all cooler days from the stack and compute the difference in indices. This is the number of days to wait.

Trapping Rain Water

Given an array of bar heights, compute how much water can be trapped between the bars after rain. A monotonic stack helps find, for each position, the left and right boundaries that hold water.

Use an increasing stack. When a bar taller than the stack top is found, pop the stack (this is the bottom of a potential water pocket). The width is the distance between the current index and the new stack top minus 1. The height is the minimum of the two boundaries minus the popped bar. Visual analogy: water filling between walls

Why Monotonic Stacks Are O(n)

At first glance, the nested while loop inside the for loop looks like O(n^2). But it is not. Each element is pushed onto the stack exactly once. Each element is popped at most once. The total number of push and pop operations across the entire algorithm is at most 2n. Dividing the total work by n elements gives O(n) time complexity.

Operation	Count
Push operations	At most n (one per element)
Pop operations	At most n (each element popped at most once)
Total operations	At most 2n
Time complexity	O(n)

Learn about time complexity in detail

Implementation Template

This pseudocode works for most monotonic stack problems:

function monotonicStack(arr):
    stack = empty stack
    result = array of -1s with length n

    for i from 0 to n-1:
        while stack is not empty AND arr[i] > arr[stack.top()]:
            index = stack.pop()
            result[index] = arr[i]   // or i, depending on the problem

        stack.push(i)

    return result

To find next smaller elements, change the comparison to arr[i] < arr[stack.top()]. To store distances instead of values, adjust the result assignment accordingly.

Code Example in Python

def next_greater_elements(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

print(next_greater_elements([2, 1, 2, 4, 3]))
# Output: [4, 2, 4, -1, -1]

When to Recognize This Pattern

Frequently Asked Questions

When should I use a monotonic stack?

Use a monotonic stack when you need to find the next greater or next smaller element for each position in an array, or when computing nearest larger/smaller neighbors. Common problem keywords include "next greater element", "largest rectangle", "trapping rain water", and "daily temperatures".

Why is a monotonic stack O(n)?

Each element is pushed onto the stack exactly once and popped at most once. Even though there is a while loop inside the for loop, the total number of push and pop operations across the entire algorithm is at most 2n, giving O(n) time complexity.

What is the difference between a monotonic increasing and decreasing stack?

A monotonic decreasing stack keeps elements in decreasing order from bottom to top. It is used to find the next greater element. A monotonic increasing stack keeps elements in increasing order from bottom to top. It is used to find the next smaller element. The choice depends on what relationship you are looking for.