Introduction to Monotonic Stack

The inner while looks like it makes this quadratic, and it does not. Each index is pushed exactly once and popped at most once across the whole run. So the total work is O(N), and the space is O(N) for the stack.

Store indices rather than values. You almost always need the distance or the position, and you can read the value from the index whenever you want.

Recognize it when

Use a Monotonic Stack when the question shows these signs.

• You need the next or previous greater or smaller element, for every position.
• The wording is about waiting, spans, or how far until something happens.
• You are asked how much each element contributes across all subarrays, as a minimum or a maximum.
• You are removing characters or digits to make a result as small or as large as possible.
• Your first idea is for each element, scan forward until a condition holds.

It is not this pattern when:

• You need the maximum inside a fixed window that slides. That is a Monotonic Queue, which pops from both ends.
• Only the most recent item matters, with no ordering rule. That is a plain stack.
• The array is sorted already, which usually means Two Pointers or Binary Search.

The template

function nextGreater(values):
    answer = array of "none", same length as values
    stack   = empty            # holds indices, kept decreasing by value

    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            # or values[i], depending on the question
        push i onto stack

    return answer                        # anything left on the stack keeps "none"

Two decisions define the problem. The comparison operator sets the direction. Using > keeps the stack decreasing and finds the next greater element. Using < keeps it increasing and finds the next smaller one. The line inside the while decides what an answer looks like. That may be a distance, a value, or a running total.

Variants in this chapter

The first row is the one to learn. The others change what happens during the pop, not the loop around it.

Watch out for

• Choosing the wrong direction. A decreasing stack answers "next greater" and an increasing stack answers "next smaller". Write down which one the question needs before you write the loop.
• Storing values instead of indices. Values alone cannot give you a distance, and duplicated values become impossible to tell apart.
• Forgetting the leftovers. Whatever remains on the stack at the end never found an answer, and those positions need a default such as zero or minus one.
• Getting duplicates wrong. With equal values, > and >= give different results. Decide whether an equal value counts as an answer before choosing the operator.
• Assuming the nested loop is quadratic. Every index is pushed once and popped once, so the whole scan stays linear.

How this compares with nearby patterns

The Monotonic Queue chapter later in this course is the same idea with one change. A queue can drop items from the front as well as the back, which is what lets it forget elements that have left the window.

Key Takeaways

• The stack holds items that are still waiting for an answer, and they are always in sorted order.
• Popping before pushing keeps that order, and every pop resolves one waiting item.
• Store indices, because distances and positions are usually what the question wants.
• The scan is O(N), since each index is pushed once and popped once.
• The comparison operator chooses the direction, and the body of the pop chooses the answer.

Let's apply it to the first problem, Remove Nodes From Linked List.