Introduction to Monotonic Stack

The code contains a while loop inside a for loop, but the total time is not O(N²).

Each index is pushed exactly once. Each index is popped at most once. Therefore, the total time complexity is O(N).

The stack may store all indices in the worst case, so the space complexity is O(N).

Store indices because they provide both position and value. The value can be read as temperatures[index].

Recognize it when

A Monotonic Stack may be useful when:

• The problem asks for the next greater or next smaller value.
• The problem asks for the previous greater or previous smaller value.
• The wording asks how long you must wait.
• The answer is a distance, span, or nearest position.
• Each element contributes as a minimum or maximum across subarrays.
• You remove digits or values to make a result as small or large as possible.
• Your first solution scans forward from every position.

Do not use this pattern when:

• Only the most recent item matters and no sorted order is required. Use a basic Stack.
• You need a maximum or minimum inside a moving window. Use a Monotonic Queue.
• The input is already sorted and you need a target. Use Binary Search or Two Pointers.
• You need a general sorted collection with insert and delete operations. Use another ordered data structure.

The template

function nextGreater(values):
    answer = array filled with a default value
    stack = empty

    for i from 0 to length(values) - 1:
        while stack is not empty and values[i] > values[top of stack]:
            j = pop from stack
            answer[j] = i - j

        push i onto stack

    return answer

Two choices define the problem:

1. The comparison operator decides whether the stack increases or decreases.
2. The code inside the pop decides what answer to record.

Using > finds the next greater value and keeps waiting values in decreasing order.

Using < finds the next smaller value and keeps waiting values in increasing order.

The answer may be a distance, a value, an index, or a contribution to a total.

Variants in this chapter

Learn the next-greater variant first. The other variants change the work performed during each pop.

Watch out for

• Choosing the wrong direction. Decide whether you need greater or smaller values before choosing the comparison.
• Storing only values. Store indices when you need distances or must distinguish duplicate values.
• Forgetting unanswered positions. Items left in the stack never found a matching future value.
• Handling equal values incorrectly. > and >= produce different answers when duplicates exist.
• Calling the algorithm quadratic. Every index is pushed once and popped at most once.
• Reading the top of an empty stack. Always check that the stack contains an item first.

How this compares with nearby patterns

A Monotonic Queue also keeps items ordered. It can remove items from the front when they leave a sliding window.

Key takeaways

• A monotonic stack keeps waiting items in increasing or decreasing order.
• Pop items that break the required order before pushing the current item.
• A pop usually completes one waiting answer.
• Store indices when the answer needs positions or distances.
• Each index is pushed once and popped at most once.
• The total time is O(N), and the worst-case space is O(N).

Now apply this pattern to Remove Nodes From Linked List.