LeetCode 20 - Valid Parentheses

The problem gives a string containing only six possible characters: (, ), {, }, [ and ]. Each opening bracket must eventually be matched with the correct closing bracket, and the order of matching matters.

leetcodeeasystringstack

LeetCode Problem 20

Difficulty: 🟢 Easy
Topics: String, Stack

Solution

Problem Understanding

The problem gives a string containing only six possible characters: (, ), {, }, [ and ]. Each opening bracket must eventually be matched with the correct closing bracket, and the order of matching matters.

A string is considered valid only if every opening bracket is closed by the same type of bracket and the nesting order is correct. This means brackets behave like nested containers. For example, "([])" is valid because the square brackets are fully opened and closed before the parentheses close. However, "([)]" is invalid because the closing order does not match the opening order.

The input represents a sequence of bracket operations. Opening brackets begin a new nested scope, while closing brackets attempt to close the most recently opened scope. The expected output is a boolean value:

  • true if the entire string follows valid matching rules
  • false otherwise

The constraints tell us the string length can be as large as 10^4. This is small enough for linear time solutions to run comfortably, but large enough that repeatedly rescanning or rebuilding strings inefficiently would be unnecessary overhead.

Several edge cases are important:

  • A closing bracket appearing before any opening bracket, such as "]", is immediately invalid.
  • A mismatched pair like "(]" must be detected correctly.
  • Correct nesting matters, so "([)]" is invalid even though the counts match.
  • Extra opening brackets left over at the end, such as "(((", make the string invalid.
  • The problem guarantees the string contains only bracket characters, so we do not need to handle letters, digits, or whitespace.

Approaches

Brute Force Approach

A brute force strategy repeatedly removes valid adjacent bracket pairs from the string. For example, if the string contains "()", "[]", or "{}", those substrings can be deleted. This process continues until either the string becomes empty or no more removals are possible.

For example:

  • "([])" becomes "()"
  • "()" becomes ""
  • Empty string means valid

This works because every valid nested structure eventually reduces to an empty string when matching pairs are removed layer by layer.

However, this approach is inefficient because every removal operation creates a new string and requires rescanning the remaining characters. In the worst case, the algorithm repeatedly traverses nearly the entire string many times, leading to quadratic time complexity.

Optimal Approach

The key insight is that bracket validation naturally follows a Last In, First Out behavior. The most recently opened bracket must always be the first one closed.

This is exactly the behavior of a stack.

Whenever we encounter an opening bracket, we push it onto the stack because it still needs a matching closing bracket later. When we encounter a closing bracket, we check whether it matches the most recent unmatched opening bracket on the stack.

If at any point the match fails, the string is invalid immediately. After processing the entire string, the stack must be empty for the string to be valid.

This allows us to solve the problem in a single pass through the string.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly removes matching pairs from the string
Optimal O(n) O(n) Uses a stack to track unmatched opening brackets

Algorithm Walkthrough

  1. Create a stack to store opening brackets that have not yet been matched.
  2. Create a hash map that maps each closing bracket to its corresponding opening bracket. This allows constant time matching checks.
  3. Iterate through each character in the string.
  4. If the current character is an opening bracket, push it onto the stack because it must be matched later.
  5. If the current character is a closing bracket, first check whether the stack is empty. If it is empty, there is no opening bracket available to match, so return False.
  6. Otherwise, pop the top element from the stack. This represents the most recent unmatched opening bracket.
  7. Compare the popped opening bracket with the expected opening bracket from the hash map. If they do not match, return False.
  8. Continue processing until all characters have been examined.
  9. After the loop finishes, check whether the stack is empty. If any opening brackets remain unmatched, return False. Otherwise, return True.

Why it works

The algorithm maintains an important invariant: the stack always contains the unmatched opening brackets in the exact order they must be closed. Because brackets must close in reverse order of opening, the most recently opened bracket must always be matched first. The stack enforces this ordering automatically. If every closing bracket matches correctly and the stack is empty at the end, then every bracket pair is properly matched and ordered.

Python Solution

class Solution:
    def isValid(self, s: str) -> bool:
        stack: list[str] = []

        bracket_map = {
            ')': '(',
            ']': '[',
            '}': '{'
        }

        opening_brackets = {'(', '[', '{'}

        for char in s:
            if char in opening_brackets:
                stack.append(char)
            else:
                if not stack:
                    return False

                top = stack.pop()

                if top != bracket_map[char]:
                    return False

        return len(stack) == 0

The implementation begins by creating an empty stack. This stack stores opening brackets that still need matching closing brackets later in the string.

The bracket_map dictionary maps each closing bracket to the opening bracket it expects. This makes matching efficient because we can directly compare the current closing bracket against the most recent opening bracket.

The opening_brackets set allows fast checking of whether the current character is an opening bracket.

As the algorithm iterates through the string:

  • Opening brackets are pushed onto the stack.
  • Closing brackets trigger validation logic.

When processing a closing bracket, the algorithm first ensures the stack is not empty. An empty stack would mean there is no opening bracket available to match.

Next, the algorithm pops the most recent opening bracket and compares it against the expected match from bracket_map. If the brackets do not match, the string is invalid immediately.

Finally, after processing all characters, the stack must be empty. Any remaining opening brackets indicate incomplete matching.

Go Solution

func isValid(s string) bool {
    stack := []rune{}

    bracketMap := map[rune]rune{
        ')': '(',
        ']': '[',
        '}': '{',
    }

    openingBrackets := map[rune]bool{
        '(': true,
        '[': true,
        '{': true,
    }

    for _, char := range s {
        if openingBrackets[char] {
            stack = append(stack, char)
        } else {
            if len(stack) == 0 {
                return false
            }

            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            if top != bracketMap[char] {
                return false
            }
        }
    }

    return len(stack) == 0
}

The Go solution follows the same logic as the Python implementation, but uses slices to implement the stack. Appending to the slice pushes onto the stack, and slicing off the last element performs the pop operation.

Go does not have Python-style sets, so a map[rune]bool is used to represent the collection of opening brackets.

The algorithm uses rune instead of byte for clarity and correctness with character handling, although this specific problem only contains ASCII characters.

Worked Examples

Example 1

Input: s = "()"

Step Character Action Stack Result
1 ( Push opening bracket ['('] Continue
2 ) Pop and compare [] Match
End - Stack empty [] True

Final output: true

Example 2

Input: s = "()[]{}"

Step Character Action Stack Result
1 ( Push ['('] Continue
2 ) Pop and match [] Match
3 [ Push ['['] Continue
4 ] Pop and match [] Match
5 { Push ['{'] Continue
6 } Pop and match [] Match

Final output: true

Example 3

Input: s = "(]"

Step Character Action Stack Result
1 ( Push ['('] Continue
2 ] Pop and compare [] Mismatch

Expected opening bracket for ] is [, but stack contains (.

Final output: false

Example 4

Input: s = "([])"

Step Character Action Stack Result
1 ( Push ['('] Continue
2 [ Push ['(', '['] Continue
3 ] Pop and match ['('] Match
4 ) Pop and match [] Match

Final output: true

Example 5

Input: s = "([)]"

Step Character Action Stack Result
1 ( Push ['('] Continue
2 [ Push ['(', '['] Continue
3 ) Pop and compare ['('] Mismatch

The algorithm expects ( before ), but the top of the stack is [.

Final output: false

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed once
Space O(n) Stack may store all opening brackets

The algorithm performs a single pass through the string, so the runtime is linear in the number of characters. Every bracket is pushed onto or popped from the stack at most once.

The worst-case space usage occurs when the string contains only opening brackets, such as "(((((". In that case, the stack stores all characters, requiring linear extra space.

Test Cases

solution = Solution()

assert solution.isValid("()") == True          # simple valid pair
assert solution.isValid("()[]{}") == True      # multiple valid bracket types
assert solution.isValid("(]") == False         # mismatched brackets
assert solution.isValid("([])") == True        # properly nested brackets
assert solution.isValid("([)]") == False       # incorrect nesting order

assert solution.isValid("{[]}") == True        # nested different bracket types
assert solution.isValid("(") == False          # unmatched opening bracket
assert solution.isValid(")") == False          # unmatched closing bracket
assert solution.isValid("(((") == False        # only opening brackets
assert solution.isValid(")))") == False        # only closing brackets

assert solution.isValid("(([]){})") == True    # complex valid nesting
assert solution.isValid("(([]){})]") == False  # extra closing bracket
assert solution.isValid("][") == False         # closing before opening
assert solution.isValid("{{[[(())]]}}") == True # deeply nested valid structure
assert solution.isValid("{[(])}") == False     # deeply nested invalid structure
Test Why
"()" Simplest valid case
"()[]{}" Multiple independent bracket pairs
"(]" Mismatched bracket types
"([])" Correct nested structure
"([)]" Incorrect nesting order
"{[]}" Mixed nested brackets
"(" Unmatched opening bracket
")" Unmatched closing bracket
"(((" Stack never emptied
")))" Closing brackets without openings
"(([]){})" More complex valid nesting
"(([]){})]" Extra closing bracket at end
"][" Invalid ordering immediately
"{{[[(())]]}}" Deep valid nesting
"{[(])}" Deep invalid nesting

Edge Cases

One important edge case occurs when a closing bracket appears before any opening bracket, such as "]" or ")(". A naive implementation might attempt to pop from an empty stack, causing an error. This implementation explicitly checks whether the stack is empty before attempting to pop. If the stack is empty, the function immediately returns False.

Another critical edge case involves incorrect nesting order. Strings like "([)]" contain matching counts of each bracket type, but the ordering is invalid. A simple counting solution would incorrectly accept this input. The stack-based approach correctly rejects it because the most recent unmatched opening bracket must match the current closing bracket.

A third important edge case occurs when opening brackets remain unmatched at the end of processing, such as "(((" or "(()". Some implementations mistakenly return True after processing all characters without checking for leftover openings. This implementation avoids that bug by ensuring the stack is empty before returning True.

A final edge case involves deeply nested valid expressions like "{{[[(())]]}}". The implementation handles this naturally because the stack preserves the exact nesting order required for correct matching.