Stack

What it is

A stack stores items in last-in, first-out order: the most recently added item is the first one removed. Its basic operations are pushing an item, inspecting the top, and popping the top. In Python, a list supports these operations with append(), stack[-1], and pop().

Stacks are useful when processing creates unfinished work that must be resolved in reverse order. An opening delimiter waits for its matching closing delimiter. A recent action is undone before an older action. A candidate remains available until a later item makes it unnecessary.

The speedup often comes from avoiding repeated searches. Instead of rescanning earlier items, a stack retains only the relevant unresolved items. In many algorithms, each item is pushed once and popped at most once, turning a potentially quadratic process into a linear one.

How to recognize it

Look for these signals:

• Nested structure: delimiters, scopes, or tasks must close in reverse opening order.
• Undoable history: the latest action must be reversed first, possibly with redo support.
• Adjacent interactions: a new item can eliminate the most recent surviving item and then interact with the next survivor.
• Nearest greater or smaller elements: each position needs a qualifying neighbor on one or both sides.
• Contiguous interval boundaries: an element determines a minimum or maximum until a smaller or larger element blocks it.
• Greedy removal of recent choices: replacing the last selected item can improve the result, provided completion remains possible.

A stack is not appropriate merely because processing is sequential. If the oldest pending item must be handled first, use a queue. If arbitrary items must be retrieved by priority, consider a heap.

The core technique

1. Nested matching and reversible history

Use an ordinary stack when the most recent unresolved item is the only valid next item to resolve.

For delimiter matching, push opening delimiters. A closing delimiter must match the top opening delimiter. A mismatch or an empty stack means the structure is invalid; leftover openings also make it invalid.

def balanced(text):
    matching = {')': '(', ']': '[', '}': '{'}
    openings = set(matching.values())
    stack = []

    for ch in text:
        if ch in openings:
            stack.append(ch)
        elif ch in matching:
            if not stack or stack.pop() != matching[ch]:
                return False

    return not stack

This version ignores non-delimiter characters. If the input permits only delimiters, validate that restriction separately.

For reversible append history, maintain an active stack and a redo stack:

• A new append pushes onto the active stack and clears the redo stack.
• Undo moves the active top to the redo stack.
• Redo moves the redo top back to the active stack.

Clearing redo matters: a new action after undo creates a new branch of history. For actions more complex than appending, stack entries must contain enough information to reverse and replay each action.

2. Surviving-record simulation

Use a stack when interactions occur only between adjacent surviving records.

Process records from left to right. Treat the incoming record as unresolved and compare it with the stack top. If the top is eliminated, pop it and repeat: the incoming record has become adjacent to an older survivor. If the incoming record is eliminated, stop. Otherwise, push it.

Define the interaction rules before implementing the loop. Directional records, for example, may conflict only when their directions make them move toward each other. Equal strengths may eliminate both records rather than just one.

The invariant is that the stack contains the fully resolved survivors of the processed prefix. A single incoming record can trigger many pops, but each previous survivor can be removed only once.

3. Monotonic stacks

A monotonic stack keeps its values ordered by removing candidates that cannot help future queries. Store indices when answers depend on positions, distances, or interval boundaries.

To find each element's nearest strictly greater predecessor, maintain a strictly decreasing stack of indices:

def previous_greater(values):
    answer = [-1] * len(values)
    stack = []

    for i, value in enumerate(values):
        while stack and values[stack[-1]] <= value:
            stack.pop()
        if stack:
            answer[i] = stack[-1]
        stack.append(i)

    return answer

A popped value cannot help later: the current value is at least as large and closer to every future position. After popping, the top is the nearest remaining qualifying predecessor.

For nearest smaller elements, reverse the comparison. To query successors, scan from right to left with the same reasoning, or scan forward and resolve pending indices when a qualifying value arrives.

Monotonic stacks also find the boundaries over which an element acts as an interval minimum or maximum. For a height-based interval objective, a popped height extends between its nearest smaller boundaries. With variable widths, prefix sums of widths give the interval's total width; multiply that width by the popped height.

For aggregate contributions, count how many left and right endpoints belong to each element. Equal values require a consistent ownership rule, commonly a strict boundary on one side and a non-strict boundary on the other. When duplicates are interchangeable for a counting query, equal-value groups can store a multiplicity instead of separate entries.

4. Greedy stacks with feasibility checks

Use a stack to build an ordered result when a better incoming choice can replace recent choices. Popping is safe only if the removed choice can still be supplied later or is no longer required.

For a lexicographically smallest subsequence containing every distinct label once, record each label's last occurrence and track selected labels:

def smallest_distinct(labels):
    last = {label: i for i, label in enumerate(labels)}
    stack, selected = [], set()

    for i, label in enumerate(labels):
        if label in selected:
            continue
        while stack and stack[-1] > label and last[stack[-1]] > i:
            selected.remove(stack.pop())
        stack.append(label)
        selected.add(label)

    return stack

The ordering comparison improves the prefix; the last-occurrence check preserves feasibility. The stack remains a subsequence because items are appended only in input order.

Common mistakes

• Wrong equality rule: strictly greater queries must remove equal values too.
• Using if instead of while: one item may invalidate several stack entries.
• Accessing an empty top: check the stack before indexing or popping.
• Storing values without positions: interval lengths and distances usually require indices.
• Ignoring unfinished entries: delimiter matching needs a final emptiness check; interval algorithms may need a final drain.
• Unsafe greedy popping: a smaller incoming value does not justify removing a required label that never appears again.
• Double-counting equal extrema: assign tied intervals consistently when summing contributions.

Complexity

Ordinary stack operations take amortized O(1) time with a Python list. Processing n items typically takes O(n) time and O(n) auxiliary space.

Monotonic and greedy loops remain linear despite nested while loops: each index or label occurrence is pushed at most once and popped at most once. Preliminary last-occurrence maps or prefix sums also take linear time.

Stack space can reach n when nothing is removed. Returned answer arrays require additional O(n) output space. Hash-based membership operations are expected O(1).