Valid Parentheses: Stack Pattern Explained

Valid Parentheses is one of the first stack problems most people encounter on LeetCode. It is problem number 20, it is rated Easy, and it shows up constantly in interviews. More importantly, the technique it teaches, using a stack to match pairs, is a building block that appears in dozens of harder problems later.

Let's break it down from scratch.

The problem

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

A string is valid if:

• Every opening bracket has a corresponding closing bracket of the same type.
• Brackets close in the correct order. You cannot have ([)] because the ] tries to close the [ before the ( has been closed.
• Every closing bracket has a matching opening bracket.

Examples:

• "()" is valid
• "()[]{}" is valid
• "(]" is not valid
• "({[]})" is valid (nested correctly)
• "([)]" is not valid (interleaved, not nested)

Seems simple when the strings are short. But how do you handle arbitrary nesting with an efficient algorithm?

Why a stack works for bracket matching

Think about what happens when you read brackets left to right. Each time you see an opening bracket, you need to remember it because eventually some closing bracket has to match it. And critically, the most recently opened bracket must be closed first. ({[]}) requires the [ to close before the {, which must close before the (.

That "most recent first" behavior is exactly what a stack gives you. Last in, first out. Push openers on, and when you see a closer, check whether it matches whatever is on top.

If the closer matches the top of the stack, pop and keep going. If it does not match, or if the stack is empty when you encounter a closer, the string is invalid. If you reach the end and the stack is not empty, there are unmatched openers, so the string is also invalid.

That is the entire algorithm. The stack does all the bookkeeping for you.

Visual walkthrough

Let's trace through ({[]}) step by step. Watch the stack grow as we push openers, and shrink as closers match and pop.

Every bracket found a match. The stack ended empty. The string is valid.

Notice how each character is processed exactly once, and each stack operation (push or pop) takes constant time. The whole thing runs in O(n).

The code

Here is the clean Python solution for LeetCode Valid Parentheses:

def is_valid(s: str) -> bool:
    matching = {')': '(', '}': '{', ']': '['}
    stack = []

    for ch in s:
        if ch in matching:
            # Closing bracket: check top of stack
            if not stack or stack[-1] != matching[ch]:
                return False
            stack.pop()
        else:
            # Opening bracket: push
            stack.append(ch)

    return len(stack) == 0

Let's walk through what makes this work:

• matching is a dictionary that maps each closing bracket to its expected opener. This is the core trick. Instead of writing a bunch of if/else comparisons, you do a single dictionary lookup.
• When we see a closing bracket, we check two things: is the stack non-empty, and does the top match? If either check fails, we return False immediately.
• When we see an opening bracket, we push it. No validation needed at this point.
• After processing every character, we check len(stack) == 0. If there are leftover openers, the string is invalid even though no mismatches were found along the way.

Complexity analysis

Time: O(n). We iterate through the string once. Each character triggers at most one push or one pop, both O(1). Total work is proportional to the length of the string.

Space: O(n). In the worst case, the string is all openers like ((((((, and we push every character onto the stack. So stack size can grow up to n.

There is no way to solve this problem faster than O(n) since you have to look at every character at least once. This solution is optimal.

Edge cases to watch for

These are the cases that trip people up in interviews:

• Empty string. An empty string has no unmatched brackets, so it is valid. The code handles this correctly because the loop does not execute, and len(stack) == 0 returns True.
• Single bracket. "(" is invalid (unmatched opener) and ")" is invalid (closer with no opener). The code catches both: the first leaves a non-empty stack, the second fails the not stack check.
• Only openers. "(((" processes fine through the loop but fails the final len(stack) == 0 check. Do not return True early just because no mismatches were found during iteration.
• Interleaved brackets. "([)]" is the classic trap. The ] does not match the ( on top of the stack, so the code returns False. People sometimes think "well, there is a [ somewhere" but the nesting order matters, not just the count.
• Right bracket first. ")(" fails immediately at the first character because the stack is empty when we encounter a closer.

The Building Blocks

The Valid Parentheses solution is built from one core building block that shows up across many other problems:

Stack-based parsing. The idea of walking through a sequence, pushing state onto a stack when you enter a new context, and popping when you leave it. In this problem, the "context" is an opened bracket waiting for its match. But the same push-on-enter, pop-on-exit pattern drives:

• Decode String (3[a2[bc]]): push the current string and repeat count when you see [, pop and combine when you see ]
• Basic Calculator: push the running result and sign when you see (, pop and merge when you see )
• Validate Stack Sequences: simulate push/pop operations to check if a given sequence is achievable
• Simplify Path (/a/b/../c): push directory names, pop when you see ..
• HTML/XML tag matching: same bracket matching logic, just with <tag> and </tag> instead of ( and )

The pattern is always the same structure. Open something, push. Close something, pop and validate. If the stack state is wrong at any point or at the end, the input is invalid.

Once you can write bracket matching from memory without hesitation, these harder problems become straightforward extensions of the same idea.

Problems that use the same brick

After you have the stack-based parsing pattern locked in, try these:

• Minimum Remove to Make Valid Parentheses: same matching logic, but instead of returning true/false, you track which brackets to remove
• Longest Valid Parentheses: store indices on the stack instead of characters to track the longest valid substring
• Generate Parentheses: backtracking to generate all valid strings of n pairs, using open/close counts instead of a stack
• Decode String: the state save/restore pattern from the stack patterns guide
• Basic Calculator: stack-based expression evaluation with nested parentheses

Why you will forget this (and how to fix it)

Valid Parentheses feels trivial once you see the solution. The matching dictionary, the push/pop logic, the final empty-stack check. It all makes perfect sense. But here is the thing: in three weeks, when you sit down for a phone screen and get asked to validate nested brackets, there is a real chance you freeze on the details. Was it matching[ch]? Or matching[stack[-1]]? Do I check the stack before or after popping?

That is not a failure of understanding. That is just how memory works. Recognition and recall are different skills. Reading a solution and nodding along is recognition. Producing it from scratch under pressure is recall.

Spaced repetition fixes this. You practice typing the code from memory at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the solution, not just re-read it. After a few cycles, the matching dictionary and the push/pop loop are locked in permanently. You do not fumble the details in an interview because they are second nature.

Related posts

• Stack Patterns - The full guide to stack patterns including bracket matching, monotonic stacks, and state save/restore
• Hash Map Patterns - The matching dictionary in this problem is a hash map pattern. Hash maps and stacks often work together.