← All topics

Stacks

Whenever a problem cares about 'the most recent unmatched thing,' reach for a stack: matching brackets, undo history, next-greater-element style questions. LIFO order is exactly the property that makes these fast.

Easy reps

20. Valid Parentheses

Given a string containing just '()[]{}', determine if the brackets are matched and properly nested.

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

Every opening bracket gets pushed. Every closing bracket must match whatever is currently on top of the stack -- if it doesn't, or the stack is empty, the string is invalid. A clean stack at the end means everything closed.

1047. Remove All Adjacent Duplicates In String

Given a string s, repeatedly remove adjacent pairs of identical letters until no such pair remains. Return the final string.

def remove_duplicates(s):
    stack = []
    for ch in s:
        if stack and stack[-1] == ch:
            stack.pop()
        else:
            stack.append(ch)
    return ''.join(stack)

Simulating the removals directly would require repeated passes over the string. A stack does it in one pass: a new character either cancels out the one on top, or gets pushed to wait for its own match.

Level up

Same topic, no training wheels. Solve these on your own before you check the editorial.