Monotonic Stack Patterns for Coding Interviews

A monotonic stack is a stack that maintains its elements in sorted order — either strictly increasing or strictly decreasing from bottom to top. Every time you push an element, you pop everything that violates the order. This turns brute-force O(n²) scans into O(n) because each element enters and leaves the stack at most once.

The Core Template

The pattern works whenever you need to find, for each element, the next greater, next smaller, previous greater, or previous smaller element.

Process 2: stack = [2]
Process 1: stack = [2, 1]        (1 < 2, just push)
Process 5: pop 1 → next_greater[1] = 5
pop 2 → next_greater[2] = 5
stack = [5]
Process 3: stack = [5, 3]        (3 < 5, just push)
Process 4: pop 3 → next_greater[3] = 4
stack = [5, 4]

Next Greater Element

For each element, find the first element to its right that is strictly greater.

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

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

    return result

print(next_greater_element([2, 1, 5, 3, 4]))
# [5, 5, -1, 4, -1]

Why it’s O(n): each index is pushed once and popped at most once — total operations across all iterations is 2n.

Next Smaller Element

Flip the comparison to build an increasing stack:

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

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

    return result

print(next_smaller_element([4, 2, 5, 1, 3]))
# [2, 1, 1, -1, -1]

Previous Greater Element

Iterate left to right but check the stack top directly — don’t pop answers, just read them:

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

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

    return result

print(previous_greater_element([3, 1, 5, 2, 4]))
# [-1, 3, -1, 5, 5]

Classic Problem: Largest Rectangle in Histogram

Given heights of bars in a histogram, find the area of the largest rectangle.

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    heights.append(0)

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

    heights.pop()
    return max_area

print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))
# 10 (the 5×2 rectangle from bars of height 5 and 6)

The trick: append 0 as a sentinel so every bar gets popped. When a bar is popped, its width extends from the current index back to the new stack top.

Classic Problem: Daily Temperatures

Given daily temperatures, find how many days until a warmer temperature (LeetCode 739).

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

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

    return result

print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

How to Recognize Monotonic Stack Problems

Look for these signals:

1. “Next greater / smaller element” — direct application.
2. “How many days until…” — distance to next greater.
3. “Largest rectangle” or “maximum width ramp” — area bounded by smaller neighbors.
4. “Stock span” — count of consecutive days with price ≤ today.
5. Any problem where brute force checks all elements to the right/left for the first one satisfying a comparison.

Complexity Summary

Interview Tips

• Always store indices on the stack, not values — you often need the distance or position.
• The sentinel trick (appending a 0 or -1) avoids special-casing leftover elements.
• If the problem involves a circular array, iterate 2n times using i % n.
• Practice identifying whether you need an increasing or decreasing stack: if you want the next greater, use a decreasing stack; for next smaller, use an increasing stack.
• Monotonic stack is often combined with DP — e.g., sum of subarray minimums uses both.