Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 20. Valid Parentheses

Check whether a string of parentheses/brackets is valid by ensuring every closing bracket matches the most recent unmatched opening bracket and the types and nesting order are correct. This is typically solved by tracking openings (e.g., with a stack) and verifying matching pairs.

Asked at:

DESCRIPTION

Input:

s = "()[]{}"

Output:

true

Explanation: All brackets are properly matched in pairs: () then [] then {}

Constraints:

1 <= s.length <= 10^4
s consists of parentheses only: '(', ')', '{', '}', '[', ']'
Every closing bracket must match the most recent unmatched opening bracket
The types must match: '(' with ')', '[' with ']', '{' with '}'

Understanding the Problem

Let's understand what we're being asked to do. Given a string like '([{}])', we need to verify that every closing bracket properly matches its corresponding opening bracket.

Tracing through: we see '(' (opening), then '[' (opening), then '{' (opening), then '}' (must match the most recent unmatched opening, which is '{' ✓), then ']' (must match '[' ✓), then ')' (must match '(' ✓). All matched correctly!

But consider '([)]': we see '(' opening, '[' opening, then ')' tries to close - but the most recent unmatched opening is '[', not '('! This is invalid.

Important constraint: Every closing bracket must match the most recent unmatched opening bracket, and the types must match ('(' with ')', '[' with ']', '{' with '}').

Edge cases to consider: What if we have ')(' (closing before opening)? What if we have '((' (not all brackets closed)? What if the string is empty (should that be valid)?

Building Intuition

The most recently opened bracket must match with the next closing bracket we encounter.

This creates a 'last-in, first-out' matching pattern where nested structures naturally resolve from innermost to outermost. For example, in '([{}])', the '{' opened last (among unmatched brackets) must close first.

This observation means we need a way to remember opening brackets in reverse order of how we'll match them.

The most recent opening bracket should be the easiest to access when we see a closing bracket. This 'last-in, first-out' property is exactly what makes certain data structures perfect for this problem.

Imagine a stack of plates. When you see '(', you add a plate labeled '('. When you see ')', you need to check if the top plate matches.

If it does, remove it (matched!). If not, or if no plates exist, it's invalid. This physical analogy maps perfectly to the bracket matching problem - you always deal with the most recently added item first.

Common Mistakes

Using a counter instead of a stack: counting opening vs closing brackets doesn't preserve order information needed for nested structures like '([)]'

Forgetting to check if stack is empty before popping: when encountering a closing bracket with no matching opening bracket (like ')(' or '())'), attempting to pop an empty stack causes errors

Not checking if stack is empty at the end: a string like '(((' has all opening brackets but is invalid because they're never closed

Incorrect type matching logic: forgetting to verify that the closing bracket type matches the opening bracket type on top of the stack (e.g., '(' should only match with ')', not ']' or '}')

Not handling edge cases: empty string (should return true - vacuously valid), single character (always invalid), or strings with only one type of bracket

Optimal Solution

Use a stack to track opening brackets as we scan the string left-to-right. When we encounter an opening bracket, push it onto the stack. When we encounter a closing bracket, check if the top of the stack contains the matching opening bracket. If it matches, pop the stack; if not (or if the stack is empty), the string is invalid. After processing all characters, the stack should be empty for a valid string.

Visualization

def is_valid(s):
    """
    Check if a string of parentheses/brackets is valid.
    Uses a stack to track opening brackets and verify matching pairs.
    """
    # Map closing brackets to their corresponding opening brackets
    bracket_map = {')': '(', '}': '{', ']': '['}
    
    # Initialize stack to track opening brackets
    stack = []
    
    # Scan each character in the string
    for char in s:
        # If it's a closing bracket
        if char in bracket_map:
            # Check if stack is empty or top doesn't match
            if not stack or stack[-1] != bracket_map[char]:
                return False
            # Pop the matching opening bracket
            stack.pop()
        else:
            # It's an opening bracket, push to stack
            stack.append(char)
    
    # Valid if stack is empty (all brackets matched)
    return len(stack) == 0

Start validating parentheses string

0 / 21

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We scan through each character in the string exactly once, performing constant-time stack operations (push/pop) for each character

Space Complexity: O(n) In the worst case (all opening brackets like '(((('), we store all n characters on the stack before encountering any closing brackets

What We've Learned

Stack for nested matching: Whenever you encounter problems with paired symbols that must match in reverse order (last opened, first closed), a stack is the natural choice because its LIFO property mirrors the nesting structure - opening brackets push, closing brackets pop and validate.
HashMap for O(1) pair lookup: Use a dictionary/map to store bracket pairs (closing bracket as key, opening as value) rather than multiple if-statements - this makes validation a single lookup operation and keeps the code clean and extensible for new bracket types.
Early termination optimization: Check for mismatched closing brackets immediately when popping from the stack, and verify the stack is empty at the end - both conditions must be true for validity, and failing either means you can return false without further processing.
Empty stack edge case: The most common bug is popping from an empty stack when encountering a closing bracket with no matching opener - always check `if stack is empty` before popping to avoid runtime errors, or handle the exception gracefully.
Balanced structure validation pattern: This stack-based matching technique extends beyond brackets to any hierarchical validation problem: HTML/XML tag matching, function call validation, expression parsing, and even checking balanced chemical equations - recognize the pattern of "things that open must close in reverse order".
Space-time tradeoff awareness: The O(n) space for the stack is necessary and optimal - you cannot validate nested structures in less space because you must remember all unmatched opening brackets until their closers appear, making this the most efficient possible solution at O(n) time and O(n) space.

Test Your Understanding

Why is stack the right data structure for this problem?

stack provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid October, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More