Monotonic Stack: The Pattern Behind 'Next Greater Element' and So Much More

The monotonic stack is one of the most underrated patterns in competitive programming and interviews. It solves a specific family of problems — anything involving "next greater element," "previous smaller element," or "how far can I extend left/right before hitting something bigger/smaller" — and it solves them all in O(n) with a simple, elegant template.

Once you see the pattern, you'll recognize it in problems you previously thought required nested loops.

The Core Problem: Next Greater Element

Given an array, for each element, find the next element to its right that is strictly greater.

Brute force: for each element, scan right until you find a greater one. O(n^2) worst case.

Monotonic stack: O(n).

def next_greater_element(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # stores indices

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

return result

Walk through an example. Array: [2, 1, 2, 4, 3].

• i=0: stack empty. Push 0. Stack: [0]
• i=1: arr[1]=1 <= arr[0]=2. Push 1. Stack: [0, 1]
• i=2: arr[2]=2 > arr[1]=1. Pop 1, result[1]=2. arr[2]=2 <= arr[0]=2. Push 2. Stack: [0, 2]
• i=3: arr[3]=4 > arr[2]=2. Pop 2, result[2]=4. arr[3]=4 > arr[0]=2. Pop 0, result[0]=4. Push 3. Stack: [3]
• i=4: arr[4]=3 <= arr[3]=4. Push 4. Stack: [3, 4]

Result: [4, 2, 4, -1, -1]. Correct.

Why It's O(n)

The key insight: each element is pushed onto the stack exactly once and popped at most once. The inner while loop might pop multiple elements, but each element can only be popped once total across the entire algorithm. So the total number of operations (pushes + pops) is at most 2n. That's O(n).

This is the same amortization argument that makes the two-pointer technique O(n). Don't be fooled by the nested loop — it's a loop inside a loop, but the total work is linear.

Monotonic Decreasing Stack

The example above maintains a monotonically decreasing stack — elements in the stack from bottom to top are in decreasing order. When we encounter a larger element, we pop everything smaller.

This variant finds the next greater element for each position.

Monotonic Increasing Stack

Flip it: maintain a stack where elements are in increasing order from bottom to top. Pop when you encounter a smaller element.

This variant finds the next smaller element for each position.

def next_smaller_element(arr):
    n = len(arr)
    result = [-1] * n
    stack = []

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

return result

Same template, just flip the comparison from > to <.

Previous Greater/Smaller Elements

Want the previous greater element instead of the next? Scan from left to right, but peek at the top of the stack to find the answer.

def previous_greater_element(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # monotonically decreasing stack

for i in range(n):
        while stack and arr[stack[-1]] <= arr[i]:
            stack.pop()
        if stack:
            result[i] = arr[stack[-1]]
        stack.append(i)

return result

Or scan from right to left to find the previous smaller element. The four variants are:

What you need	Stack order	Direction
Next greater	Decreasing	Left to right
Next smaller	Increasing	Left to right
Previous greater	Decreasing	Left to right (peek stack top)
Previous smaller	Increasing	Left to right (peek stack top)

You can also achieve any variant by scanning in reverse. The template stays the same.

Classic Problems

Daily Temperatures

Given an array of daily temperatures, for each day, find how many days you have to wait until a warmer temperature. If no warmer day exists, output 0.

This is literally "next greater element, but return the distance."

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []

for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            idx = stack.pop()
            result[idx] = i - idx  # distance, not value
        stack.append(i)

return result

Largest Rectangle in Histogram

Given an array of bar heights, find the area of the largest rectangle that fits in the histogram. This is one of the most classic monotonic stack problems.

For each bar, you need to know how far it can extend left and right — i.e., the nearest shorter bar on each side. That's "previous smaller" and "next smaller."

def largest_rectangle_area(heights):
    n = len(heights)
    stack = []
    max_area = 0

for i in range(n + 1):
        h = heights[i] if i < n else 0  # sentinel value

while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)

stack.append(i)

return max_area

The trick: append a sentinel value of 0 at the end to flush all remaining elements from the stack. When we pop a bar, the current index i is the right boundary (the next shorter bar), and the new stack top is the left boundary (the previous shorter bar). The width is i - stack[-1] - 1.

This is O(n) — each bar is pushed and popped at most once.

Maximal Rectangle in a Binary Matrix

Given a binary matrix, find the largest rectangle containing only 1s. Build a histogram for each row (treating consecutive 1s as bar heights), then apply the largest rectangle in histogram algorithm for each row.

def maximal_rectangle(matrix):
    if not matrix:
        return 0

cols = len(matrix[0])
    heights = [0] * cols
    max_area = 0

for row in matrix:
        for j in range(cols):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0

max_area = max(max_area, largest_rectangle_area(heights))

return max_area

O(rows * cols) total. Each row builds the histogram in O(cols) and finds the largest rectangle in O(cols).

Trapping Rain Water

Given elevation bars, compute how much water can be trapped after raining. This can be solved multiple ways (two pointers, prefix max arrays), but the monotonic stack approach is particularly elegant.

def trap(height):
    stack = []
    water = 0

for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:
                break
            width = i - stack[-1] - 1
            bounded_height = min(height[i], height[stack[-1]]) - height[bottom]
            water += width * bounded_height

stack.append(i)

return water

The stack tracks bars in decreasing order. When we find a taller bar, we pop shorter bars and compute the water trapped between the current bar, the popped bar (the bottom), and the new stack top (the left wall). We compute water layer by layer, from bottom to top.

Stock Span Problem

Given daily stock prices, for each day, find the span — how many consecutive days (including today) the price has been less than or equal to today's price.

def stock_span(prices):
    n = len(prices)
    span = [0] * n
    stack = []  # monotonically decreasing stack

for i in range(n):
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()
        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)

return span

The span for day i is the distance to the previous day with a strictly greater price. That's "previous greater element, return the distance."

Sum of Subarray Minimums

Given an array, find the sum of the minimum of every contiguous subarray. For each element, determine how many subarrays it's the minimum of by finding the nearest smaller element on both sides.

def sum_subarray_mins(arr):
    n = len(arr)
    MOD = 10**9 + 7

# previous less element (strictly less)
    prev_less = [-1] * n
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        prev_less[i] = stack[-1] if stack else -1
        stack.append(i)

# next less element (less or equal, to avoid double counting)
    next_less = [n] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        next_less[i] = stack[-1] if stack else n
        stack.append(i)

result = 0
    for i in range(n):
        left_count = i - prev_less[i]
        right_count = next_less[i] - i
        result = (result + arr[i]  left_count  right_count) % MOD

return result

For each element, it's the minimum of left_count * right_count subarrays (all combinations of left and right boundaries that include this element and no smaller element). The strict vs. non-strict comparison on each side prevents double-counting when there are equal elements.

The Template

Almost every monotonic stack problem follows this pattern:

stack = []
for i in range(n):
    while stack and comparison(arr[i], arr[stack[-1]]):
        idx = stack.pop()
        # process idx: compute something using i (right boundary)
        # and stack[-1] (left boundary, if stack is non-empty)
    stack.append(i)

The three things that change between problems:

1. Comparison direction — > for next greater, < for next smaller
2. What you compute when popping — the answer for the popped element
3. Left-to-right or right-to-left — determines whether you're finding "next" or "previous"

Everything else is structural.

Common Mistakes

Forgetting to store indices, not values. Always push indices onto the stack, not values. You need the index to compute distances and to look up the value when needed. Off-by-one in width calculations. When computing the width of a rectangle or the span of a range, draw it out on paper. The formula is usually i - stack[-1] - 1 (exclusive on both boundaries), but edge cases when the stack is empty require special handling. Not handling equal elements correctly. "Next greater" usually means strictly greater. If you need "greater or equal," change the comparison. For problems like sum of subarray minimums, you need one side strict and one side non-strict to handle duplicates without double-counting. Not adding a sentinel value. For histogram-type problems, appending a 0 at the end forces all remaining elements to be popped and processed. Without it, elements left in the stack at the end won't have their answers computed.

The Mental Model

Think of the monotonic stack as a bouncer at a club with a strict dress code. The stack maintains an order (decreasing or increasing). When a new element arrives that violates the order, the bouncer kicks out everyone who doesn't belong until order is restored. Each eviction triggers a computation — that's where your answer comes from.

The efficiency comes from the fact that everyone enters once and gets kicked out at most once. Two operations per person, no matter how many evictions happen at any given moment.

Practice the template on CodeUp — start with next greater element, then try daily temperatures, then histogram, then trapping rain water. The progression builds intuition for how the same structure solves increasingly tricky problems. Once the template is second nature, recognizing monotonic stack problems becomes the only real challenge.