Stack Next Greater Element & Monotonic Stacks

The Next Greater Element problem is one of the most common stack questions in interviews. It seems like it needs O(n^2) — for each element, scan right to find something bigger. But a monotonic stack solves it in O(n). Once you understand this pattern, you can solve a whole family of problems.

The Problem

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

Input:  [4, 5, 2, 10, 8]
Output: [5, 10, 10, -1, -1]

Explanation:
  4 → next greater is 5
  5 → next greater is 10
  2 → next greater is 10
  10 → no greater element to the right → -1
  8 → no greater element to the right → -1

Brute Force: O(n^2)

def next_greater_brute(arr):
    """O(n^2) — for each element, scan right."""
    n = len(arr)
    result = [-1] * n
    for i in range(n):
        for j in range(i + 1, n):
            if arr[j] > arr[i]:
                result[i] = arr[j]
                break
    return result

Monotonic Stack: O(n)

The key insight: maintain a stack of elements that haven’t found their next greater element yet. When we encounter a larger element, we resolve all waiting elements that are smaller.

Right-to-left approach

def next_greater_element(arr):
    """
    Next Greater Element using monotonic stack (right to left).
    Time: O(n), Space: O(n)
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # Monotonic decreasing stack

    for i in range(n - 1, -1, -1):
        # Pop elements smaller than or equal to current
        while stack and stack[-1] <= arr[i]:
            stack.pop()

        # If stack is not empty, top is the next greater
        if stack:
            result[i] = stack[-1]

        # Push current element
        stack.append(arr[i])

    return result


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

Left-to-right approach (index-based)

def next_greater_element_lr(arr):
    """
    Next Greater Element — left to right, storing indices.
    Time: O(n), Space: O(n)
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # Stack of indices

    for i in range(n):
        # Current element is the NGE for all smaller elements on stack
        while stack and arr[i] > arr[stack[-1]]:
            idx = stack.pop()
            result[idx] = arr[i]

        stack.append(i)

    return result


print(next_greater_element_lr([4, 5, 2, 10, 8]))
# [5, 10, 10, -1, -1]

Why is this O(n)?

Even though there is a while loop inside the for loop, each element is pushed onto the stack exactly once and popped at most once. Total push operations: n. Total pop operations: at most n. Total work: O(2n) = O(n).

What is a Monotonic Stack?

A monotonic stack maintains elements in a specific order:

• Monotonic decreasing: Each new element is smaller than or equal to the top. Used for next greater problems.
• Monotonic increasing: Each new element is larger than or equal to the top. Used for next smaller problems.

# Monotonic decreasing stack property:
# stack = [10, 7, 3]  (bottom to top)
# New element 5: pop 3, stack becomes [10, 7, 5]
# New element 2: just push, stack becomes [10, 7, 5, 2]

Next Smaller Element

Same pattern, but we look for the first smaller element to the right:

def next_smaller_element(arr):
    """
    Next Smaller Element using monotonic increasing stack.
    Time: O(n), Space: O(n)
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # Monotonic increasing stack

    for i in range(n - 1, -1, -1):
        # Pop elements greater than or equal to current
        while stack and stack[-1] >= arr[i]:
            stack.pop()

        if stack:
            result[i] = stack[-1]

        stack.append(arr[i])

    return result


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

Previous Greater Element

Look left instead of right:

def previous_greater_element(arr):
    """
    Previous Greater Element — scan left to right.
    Time: O(n), Space: O(n)
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # Monotonic decreasing

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

        if stack:
            result[i] = stack[-1]

        stack.append(arr[i])

    return result


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

The Four Variants — Template

Problem	Direction	Stack Order	Compare
Next Greater	Right to left	Decreasing	Pop if <=
Next Smaller	Right to left	Increasing	Pop if >=
Previous Greater	Left to right	Decreasing	Pop if <=
Previous Smaller	Left to right	Increasing	Pop if >=

Next Greater Element II: Circular Array

In a circular array, the element after the last one is the first one. We simulate this by iterating through the array twice:

def next_greater_circular(arr):
    """
    Next Greater Element in a circular array.
    Time: O(n), Space: O(n)
    """
    n = len(arr)
    result = [-1] * n
    stack = []

    # Iterate through the array twice
    for i in range(2 * n - 1, -1, -1):
        idx = i % n

        while stack and stack[-1] <= arr[idx]:
            stack.pop()

        if stack:
            result[idx] = stack[-1]

        stack.append(arr[idx])

    return result


print(next_greater_circular([1, 2, 1]))
# [2, -1, 2]  — the 1 at index 2 wraps around to find 2 at index 1

print(next_greater_circular([5, 4, 3, 2, 1]))
# [-1, 5, 5, 5, 5]  — everything wraps around to 5

Stock Span Problem

The stock span for day i is the number of consecutive days before it (including today) where the price was less than or equal to today’s price.

def stock_span(prices):
    """
    Stock span — consecutive days with price <= today.
    Time: O(n), Space: O(n)
    """
    n = len(prices)
    spans = [0] * n
    stack = []  # Stack of indices (monotonic decreasing by price)

    for i in range(n):
        # Pop all days with price <= current
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()

        # Span = distance from previous greater price day
        spans[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)

    return spans


print(stock_span([100, 80, 60, 70, 60, 75, 85]))
# [1, 1, 1, 2, 1, 4, 6]
# Day 6 (price=85): days 1-6 all have price ≤ 85, span = 6

Daily Temperatures

Find how many days you need to wait for a warmer temperature:

def daily_temperatures(temps):
    """
    For each day, how many days until a warmer temperature?
    Time: O(n), Space: O(n)
    """
    n = len(temps)
    result = [0] * n
    stack = []  # Stack of indices

    for i in range(n):
        while stack and temps[i] > temps[stack[-1]]:
            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]

Largest Rectangle in Histogram

This classic problem uses a monotonic stack to find the largest rectangle:

def largest_rectangle_histogram(heights):
    """
    Find the largest rectangle in a histogram.
    Time: O(n), Space: O(n)
    """
    stack = []  # Monotonic increasing stack of indices
    max_area = 0
    n = len(heights)

    for i in range(n + 1):
        current_height = heights[i] if i < n else 0

        while stack and current_height < 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


print(largest_rectangle_histogram([2, 1, 5, 6, 2, 3]))
# 10 (rectangle of height 5, width 2 at positions 2-3)

Monotonic Stack Template

Here is a reusable template you can adapt:

def monotonic_stack_template(arr, find="next_greater"):
    """
    Generic monotonic stack template.
    find: "next_greater", "next_smaller", "prev_greater", "prev_smaller"
    """
    n = len(arr)
    result = [-1] * n
    stack = []

    # Determine direction and comparison
    if find.startswith("next"):
        indices = range(n - 1, -1, -1)  # right to left
    else:
        indices = range(n)  # left to right

    if "greater" in find:
        should_pop = lambda top, curr: top <= curr
    else:
        should_pop = lambda top, curr: top >= curr

    for i in indices:
        while stack and should_pop(stack[-1], arr[i]):
            stack.pop()

        if stack:
            result[i] = stack[-1]

        stack.append(arr[i])

    return result


arr = [4, 5, 2, 10, 8]
print("Next Greater: ", monotonic_stack_template(arr, "next_greater"))
print("Next Smaller: ", monotonic_stack_template(arr, "next_smaller"))
print("Prev Greater: ", monotonic_stack_template(arr, "prev_greater"))
print("Prev Smaller: ", monotonic_stack_template(arr, "prev_smaller"))

Complexity Summary

Problem	Time	Space
Next Greater Element	O(n)	O(n)
Next Smaller Element	O(n)	O(n)
Next Greater Circular	O(n)	O(n)
Stock Span	O(n)	O(n)
Daily Temperatures	O(n)	O(n)
Largest Rectangle	O(n)	O(n)

All are O(n) because each element is pushed and popped at most once.

Practice Problems

1. LeetCode 496 — Next Greater Element I: Basic NGE with two arrays (Easy)
2. LeetCode 503 — Next Greater Element II: Circular array variant (Medium)
3. LeetCode 739 — Daily Temperatures: Days until warmer (Medium)
4. LeetCode 901 — Online Stock Span: Streaming stock span (Medium)
5. LeetCode 84 — Largest Rectangle in Histogram: Classic monotonic stack (Hard)
6. LeetCode 42 — Trapping Rain Water: Can be solved with monotonic stack (Hard)
7. LeetCode 907 — Sum of Subarray Minimums: Next/prev smaller combo (Medium)

Key Takeaways

• A monotonic stack maintains elements in sorted order by popping elements that violate the ordering.
• Each element is pushed once and popped at most once, giving O(n) total time despite the inner while loop.
• Four variants (next/prev + greater/smaller) cover most monotonic stack problems.
• For circular arrays, iterate through the array twice using modulo indexing.
• The pattern is a building block for histogram, rain water, and subarray problems.