DSA The Monotonic Stack

The problem

Next Greater Element asks, for each value in a list, for the first larger value to its right. A value with no larger value after it answers None. The answer list lines up with the input, one answer per position.

The cases below are the ones this article uses throughout. The last case falls all the way, so every answer is None.

cases = [
    ([2, 1, 4, 3], [4, 4, None, None]),
    ([2, 1, 5, 3, 4], [5, 5, None, 4, None]),
    ([1, 2, 3, 4], [2, 3, 4, None]),
    ([5, 4, 3, 2, 1], [None, None, None, None, None]),
]
for values, expected in cases:
    print("values", values, "-> next greater:", expected)

Read one row at a time. In the first row, both 2 and 1 wait until 4 arrives. In the second row, 3 is answered by 4, while 5 is never answered at all.

Intuition: scan right, and the pattern that fixes it

The first idea scans right from each value until a larger one appears. The scan stops at the first larger value, because that value is the answer. On a short list the idea feels cheap.

The trap is a falling list. Every scan runs to the end of the list and finds nothing. The work is spent exactly where the news is bad.

values = [5, 4, 3, 2, 1]
comparisons = 0
answer = []
for i in range(len(values)):
    found = None
    for j in range(i + 1, len(values)):
        comparisons += 1
        if values[j] > values[i]:
            found = values[j]
            break
    answer.append(found)
print("answer:", answer)
print("comparisons:", comparisons)

Five values cost ten comparisons and every answer is None. The pattern that fixes this is a monotonic stack. A stack is monotonic when its values never change direction along it, and this article keeps them falling from bottom to top.

Values that are still waiting for a larger one sit on that stack. A larger arrival answers the waiters from the top down. Section 4 builds the full pattern.

Brute force: scan right from every value

The brute force is the intuition, written as a function. Each position scans right until it finds a larger value or runs out of list. A counter records every comparison.

def next_greater_brute(values):
    answer = [None] * len(values)
    comparisons = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            comparisons += 1
            if values[j] > values[i]:
                answer[i] = values[j]
                break
    return answer, comparisons

answer, comparisons = next_greater_brute([2, 1, 4, 3])
print("answer:", answer)
print("comparisons:", comparisons)
answer, comparisons = next_greater_brute([5, 4, 3, 2, 1])
print("falling answer:", answer)
print("falling comparisons:", comparisons)

The falling row pays the full comparison count. Only a complete scan from a position proves that no larger value follows it. That proof is what the stack makes cheap.

The optimal solution: a falling stack of waiting values

A decreasing stack holds the indices of values still waiting for a larger one, and each arriving value pops and answers every smaller waiter before taking its own place. That one sentence is the whole method.

Decreasing means the values fall from the bottom of the stack to the top. An arrival larger than the top breaks that order, so the top pops until the order holds again. Each popped index takes the arrival as its answer.

The stack stores indices, not values. An index names the position whose answer is being filled. The values themselves stay in the input list.

def next_greater(values):
    answer = [None] * len(values)
    stack = []
    for i, v in enumerate(values):
        while stack and values[stack[-1]] < v:
            j = stack.pop()
            answer[j] = v
        stack.append(i)
    return answer

cases = [
    ([2, 1, 4, 3], [4, 4, None, None]),
    ([2, 1, 5, 3, 4], [5, 5, None, 4, None]),
    ([1, 2, 3, 4], [2, 3, 4, None]),
    ([5, 4, 3, 2, 1], [None, None, None, None, None]),
]
for values, expected in cases:
    result = next_greater(values)
    print("values", values, "->", result, "expected:", expected, "match:", result == expected)

All four cases pass. Indices left on the stack at the end keep their starting answer of None. No larger value ever arrived for them.

Walkthrough: [2, 1, 5, 3, 4] in one pass

The walk visits one value at a time. The state is the stack of waiting indices, printed as their values after each arrival. Pops and answers happen between one printed line and the next.

values = [2, 1, 5, 3, 4]
answer = [None] * len(values)
stack = []
for i, v in enumerate(values):
    while stack and values[stack[-1]] < v:
        j = stack.pop()
        answer[j] = v
    stack.append(i)
    print("after", v, "stack:", [values[k] for k in stack])
print("next greater:", answer)

The value 5 pops both 1 and 2 and answers both. The value 4 later pops 3 and answers it. The stack ends holding 5 and 4, the two values with no greater value to their right.

Complexity

The brute force compares up to n times n minus 1, divided by 2, pairs for n values in the worst case, so its time is O(n^2). The stack pushes each index once and pops each index at most once, so its time is O(n).

The brute force stores only the answer list and its counter, so its extra space is O(1) beyond the answer. The stack holds at most one index per value, so its space is O(n).

for n in (5, 10, 20):
    values = list(range(n, 0, -1))
    comparisons = 0
    for i in range(n):
        for j in range(i + 1, n):
            comparisons += 1
            if values[j] > values[i]:
                break
    pushes = n
    pops = 0
    print("values", n, "- brute comparisons:", comparisons, " stack pushes + pops:", pushes + pops)

The falling list is the worst case for the scan and the quiet case for the stack. Nothing pops, so the stack work is one push per value. The scan count still quadruples as the list doubles.

Edge cases and pitfalls

Equal values are the classic trap. An equal value is not a greater value, so it must not pop the waiter beneath it. The pop test uses strictly smaller than the arrival, and equal values stay waiting.

Storing values instead of indices is a second trap. Two equal values would be indistinguishable, and the code could not tell which position an answer belongs to.

def next_greater(values):
    answer = [None] * len(values)
    stack = []
    for i, v in enumerate(values):
        while stack and values[stack[-1]] < v:
            j = stack.pop()
            answer[j] = v
        stack.append(i)
    return answer

print("empty list:", next_greater([]))
print("one value:", next_greater([7]))
print("all equal:", next_greater([3, 3, 3]))
print("rise then dip:", next_greater([1, 3, 2]))
print("greater on the last step:", next_greater([4, 1, 9]))

The last position always answers None until a value after it exists, and there is none. Its None comes from the starting answer list, not from a special case.