Stack

How it works

A stack holds work that is still open: brackets waiting to be closed, operands waiting for an operator, elements waiting to learn who is bigger than them. The most recent open item is always the first one that can be resolved, which is exactly last in, first out.

The monotonic stack is the version that wins interviews. Keep the stack sorted (say, decreasing). When a new element arrives, every smaller element on top has just found its next greater element, so pop and answer them. Each element is pushed once and popped once, so the whole scan is linear.

Store indices rather than values whenever the answer is a distance or a width. The index gives you both the value (by lookup) and the position.

Disguises include daily temperature waits, stock spans, the largest rectangle in a histogram, removing digits to make the smallest number, and simplifying file paths. If each element needs its nearest bigger or smaller neighbor, reach for a monotonic stack.

How to attack it

1. 1Ask what each element is waiting for; that is what sits on the stack.
2. 2Decide the stack order (increasing or decreasing) from the question.
3. 3Decide whether to store values, indices, or pairs.
4. 4Write the pop condition and the answer recorded on each pop.
5. 5Decide what to do with elements still on the stack at the end.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

def next_greater(nums):
    # Answer for each index: the next value to its right that is larger.
    result = [-1] * len(nums)
    stack = []  # indices whose answer is not known yet; values decreasing
    for i, x in enumerate(nums):
        # x resolves every smaller element still waiting on the stack.
        while stack and nums[stack[-1]] < x:
            j = stack.pop()
            result[j] = x  # or i - j for a distance
        stack.append(i)
    # Whatever remains has no greater element to the right.
    return result


def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return not stack

What it costs