Stacks and Monotonic Structures

Last opened, first resolved

A closer must match the top

For input containing only ()[]{}, push opening tokens. A closer must match the most recent unmatched opener. A nonempty stack at the end means an unclosed scope. “([)]” fails even though the total counts match: nesting order is wrong.

def is_valid_parentheses(tokens):
    matching = {')': '(', ']': '[', '}': '{'}
    stack = []
    for token in tokens:
        if token in matching:
            if not stack or stack.pop() != matching[token]:
                return False
        elif token in '([{':
            stack.append(token)
        else:
            return False
    return not stack

The alphabet contract is explicit. In a real parser, ignoring ordinary text requires lexical rules for strings, escapes and comments; this delimiter-only fragment is not a full programming-language parser. Check emptiness before accessing the top.

Store enough state to resume

For an absolute path under a simplified lexical policy, ordinary components push; “.” does nothing; “..” removes the most recent component if one exists. That does not resolve symbolic links or implement an operating system's complete path semantics.

For collisions, adjacent-pair removal or nested repeated text, store the minimum state needed to resume an unfinished process. A decoding frame may need both the outer text and repeat count, not just the last character. A collision can trigger several pops before the new object survives or disappears.

An explicit stack can replace deep recursion and avoid the language's call-depth limit. It still uses memory proportional to pending depth. Store frame position and partial result if resuming a call requires them; pushing only nodes may lose traversal order or exit work.

Operand order survives the stack

Postfix notation places operators after their operands. For “8 3 −”, pop right=3 first, then left=8; the result is 5, not −5. Multiplication and addition can hide an operand-order bug because they commute.

def eval_rpn(tokens):
    stack = []
    for token in tokens:
        if token not in ('+', '-', '*', '/'):
            stack.append(int(token))
            continue
        if len(stack) < 2:
            raise ValueError('operator needs two operands')
        right, left = stack.pop(), stack.pop()
        if token == '+': result = left + right
        elif token == '-': result = left - right
        elif token == '*': result = left * right
        else:
            magnitude = abs(left) // abs(right)
            result = -magnitude if (left < 0) != (right < 0) else magnitude
        stack.append(result)
    if len(stack) != 1:
        raise ValueError('expression must leave one result')
    return stack[0]

The evaluator accepts signed integer tokens and the four listed binary operators. Invalid integer tokens, insufficient operands and leftover operands are rejected. Division by zero raises ZeroDivisionError. Division truncates toward zero; Python // instead rounds downward. Converting left/right through floating point with int(left/right) can lose precision or overflow for huge integers.

The evaluator ends with exactly one value. A token outside the operator set must parse as an integer; it cannot silently become an operator. Arithmetic and overflow policies belong to the expression contract, not to the stack abstraction.

Keep only unresolved candidates

Scan left to right for the next strictly greater value. Keep indices whose answers remain unknown, with nonincreasing values from bottom to top. When value x arrives, pop while the top value is smaller than x. Each popped index has found its first qualifying neighbor: none of the intervening processed values qualified, or it would already have been popped.

def next_greater_indices(nums):
    answer = [None] * len(nums)
    stack = []
    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] < value:
            previous = stack.pop()
            answer[previous] = i
        stack.append(i)
    return answer

This returns neighbor indices. Convert to values or distances only afterward. None distinguishes absence from a valid negative-valued neighbor; a numeric −1 sentinel can be ambiguous when values themselves can be −1.

Equality and distance are part of the contract

Strictly greater uses a < pop test. Greater-or-equal uses ≤. Equal values may stay together or be coalesced depending on the output required. This is not a cosmetic choice: it changes answers for duplicates.

Daily-temperature waits need index distance j−i; stock spans need how far a dominance boundary lies; histogram rectangles need widths. Storing only values loses that information. Tuples can retain a height with its earliest possible start when several candidates merge.

Previous-neighbor scans pop unsuitable tops before reading the nearest remaining candidate. Next-neighbor scans resolve popped entries as the new value arrives. Distinguish which side's answers are being filled before choosing increasing versus decreasing order.

From greater neighbors to spans and rectangles

For a histogram bar of height h, a rectangle can extend until a strictly smaller boundary blocks that height. With boundaries L and R, width is R−L−1 and area is h·width. A one-pass variant carries each popped height's earliest start, then evaluates areas when a shorter height arrives.

Equal-height handling must preserve the full possible span without incorrectly double-counting index roles. A terminal sentinel lower than all legal nonnegative heights can flush pending bars, or finish with an explicit flush. Zero heights and empty input need defined behavior.

Stock-span candidates discard previous prices that cannot be the nearest greater blocker. A car-fleet problem combines sorted positions with arrival-time comparisons; its correctness also depends on no overtaking after cars meet. Do not assume the next-greater proof applies to every problem with a similar-looking stack.

A sliding-window maximum usually needs a monotonic deque, not only a stack: expired indices leave the front while newly dominated candidates leave the back. Window boundaries → determine expiration.

A nested loop can have linear total work

One incoming value can trigger O(n) pops, so a single iteration is not worst-case constant time. Summed across the scan, those pops cannot repeat for the same index. The potential “number of entries still on the stack” rises by one on a push and falls on a pop.

The monotonic algorithm uses O(n) time and O(n) worst-case pending state under constant-cost comparisons and stack operations. Generating all possible pairs or building huge decoded strings has additional output cost. A nested loop alone does not determine complexity; count events that can recur.

Say what every stack entry awaits

Test increasing, decreasing and constant inputs; duplicates; empty input; one element; malformed nesting; noncommutative expressions; and deep scopes. Name bottom-to-top order and the exact equality rule.

A useful sequence is nesting → state simulation → postfix operands → next-greater indices → spans and histogram boundaries. Generate-parentheses enumeration belongs to search/backtracking, even though a nesting condition guides it. A min stack additionally retains a minimum summary per depth; a plain stack does not make minimum queries constant time.

Related patterns and sources

Python list stack operations ↗ · Python division semantics ↗

Use Backtracking for enumerating nested choices. Use Windows and Two Pointers when expiration requires a deque.