Monotonic Stack Algorithm Tutorial

Next Greater Element (Monotonic Stack)

The Next Greater Element problem finds, for each element, the first larger element to its right. A monotonic stack solves this in $O(n)$ time by maintaining a stack of elements in decreasing order.

You process the array from right to left. For each element, you pop smaller elements (they can't be the answer for anything to the left), then the stack top is the answer.

function nextGreaterElement(arr, n):
    result = array of size n, initialized to -1
    stack = empty stack

    for i from n - 1 down to 0:
        while stack is not empty and stack.top() <= arr[i]:
            stack.pop()
        if stack is not empty:
            result[i] = stack.top()
        stack.push(arr[i])

    return result

Why this works: Your stack always contains elements in decreasing order from bottom to top. When you find an element larger than the current one, it's the first larger element to the right.

Variants: You can solve next smaller element, previous greater element, and previous smaller element with similar approaches.

Using indices: You often push indices instead of values so you can track positions or compute distances.

Applications: You use monotonic stacks for stock span problems, histogram largest rectangle, trapping rain water, and daily temperatures.

Time complexity: $O(n)$ because each element is pushed and popped at most once.

Space complexity: $O(n)$ for the stack in the worst case.