Valid Parentheses — The Locksmith's Keys

Welcome to Dungeon 3

Two dungeons down. You walked out of Dungeon 1 with hashing and Dungeon 2 with two pointers. Two weapons, two families of problems.

This dungeon gives you a third: the stack. It's a data structure, not an algorithm, but the problems it solves have a very specific flavor. Any time you see "last opened, first closed" or "what was the most recent thing?" — that's stack territory.

Seven bosses in this dungeon. Let's go.

Today's boss: The Locksmith's Keys.

The story

You walk into a locksmith's workshop. The old locksmith, Koji, is testing a new ring of keys for a client's vault. The ring has a sequence of symbols on it:

"( [ { } ] )"

Each opening bracket represents turning a key to open a lock. Each closing bracket represents turning a key to close a lock. The vault only works if every lock is closed in the exact reverse order it was opened.

"Simple enough," says Koji. "But some of these rings are damaged. I need you to check them for me."

He slides a few test rings across the counter:

"( )"       → valid
"( ] "      → invalid (opened round, closed square)
"( [ ) ]"   → invalid (opened square, but closed round first)
"{ [ ] }"   → valid
""          → valid (nothing opened, nothing to close)

You need a system that can check any ring, no matter how long, and tell Koji whether it's valid.

The problem, dressed up properly

Given a string s containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

A string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

The naive attempt (and why it's messy)

Your first thought might be: scan for pairs, remove them, repeat until nothing's left. If something remains, it's invalid.

def is_valid(s):
    while "()" in s or "[]" in s or "{}" in s:
        s = s.replace("()", "").replace("[]", "").replace("{}", "")
    return s == ""

It works! But it's slow. Each replace scans the whole string, and you might need to do it n/2 times. That's O(n²) worst case. For short strings it's fine, but it's not what we're here to learn.

The weapon: a stack

Here's the idea. Walk the string left to right. Keep a stack (a list where you only add and remove from the top).

• See an opening bracket? Push it onto the stack.
• See a closing bracket? Check: does it match the bracket on top of the stack?
  • Yes: pop the top. Keep going.
  • No: invalid. Stop immediately.
• At the end, if the stack is empty, every bracket was matched. Valid.

Watching it work

Let's trace "{ [ ] }".

char    action          stack
{       opener, push    ['{']
[       opener, push    ['{', '[']
]       closer, top='[' matches → pop   ['{']
}       closer, top='{' matches → pop   []

End: stack empty → valid ✓

Now let's trace "( [ ) ]".

char    action          stack
(       opener, push    ['(']
[       opener, push    ['(', '[']
)       closer, top='[' does NOT match ')' → invalid ✗

Caught on the third character. We expected ] to close the [, but got ) instead. Invalid.

One more: "( ( (".

char    action          stack
(       push            ['(']
(       push            ['(', '(']
(       push            ['(', '(', '(']

End: stack has 3 items → invalid ✗

Unclosed brackets. The stack isn't empty, so there are openers with no closers.

The code

def is_valid(s: str) -> bool:
    stack = []
    match = {')': '(', ']': '[', '}': '{'}
 
    for char in s:
        if char in match:
            # it's a closer
            if not stack or stack[-1] != match[char]:
                return False
            stack.pop()
        else:
            # it's an opener
            stack.append(char)
 
    return len(stack) == 0

Walk through it. The match dictionary maps each closer to the opener it expects. For every character:

• If it's a closer, check that the stack isn't empty and the top matches. If not, bail.
• If it's an opener, push it.
• At the end, the stack must be empty.

Why does this work?

The stack enforces the "last opened, first closed" rule automatically. When you push openers in order and pop them on matching closers, the stack's top always holds the most recently opened, not-yet-closed bracket. That's exactly the one that should be closed next.

This property is called LIFO — Last In, First Out. It's the defining feature of stacks, and it's the reason they solve bracket-matching problems in one clean pass.

Complexity

• Time: O(n). One pass through the string, each character is pushed or popped at most once.
• Space: O(n) worst case. If the string is all openers ("((((("), the stack grows to size n.

Compare to the replace-loop approach:

Gotchas

1. Empty stack when you see a closer. "]" has no opener at all. If you forget to check not stack before peeking, you'll crash.

2. Non-empty stack at the end. "(((" has no closers. The loop finishes without errors, but the stack still has items. You must check len(stack) == 0 at the end.

3. Mixing up the match direction. The dictionary maps closers to openers, not the other way around. ')': '(' means "when I see ), I expect ( on top." If you flip it, every valid string becomes invalid.

4. Characters other than brackets. The problem says the string only contains brackets, but if you're writing this for production code, you'd skip characters that aren't in your match dictionary.

You just picked up a new weapon

The stack is not fancy. It's a list with a discipline: you only touch the top. But that discipline is what makes it powerful. It gives you a "memory of what was most recently opened," and that memory turns a confusing scanning problem into a clean one-pass algorithm.

This same idea appears in:

• HTML tag matching
• Compiler syntax checking
• Undo/redo systems
• Call stacks in every programming language

You'll use it in every remaining boss of this dungeon.

Boss down. XP gained.

You cleared Boss 1. Koji's key rings are validated.

What you walked away with:

• A stack — the LIFO data structure
• A one-pass bracket matching algorithm
• The intuition that "last opened, first closed" = "use a stack"

Next up: Boss 2 — The Warehouse Foreman. A warehouse worker needs to know the lightest crate in the pile at any moment, without digging through the whole stack. You'll learn how to augment a stack with extra tracking so that getMin() is instant, not linear.

Meet you at the loading dock.