Skip to main content

🟩 Valid Parentheses (#20)

🔗 Problem Link​

📋 Problem Statement​

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

An input 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.

💡 Examples​

Example 1​

Input: s = "()"
Output: true

Example 2​

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

Example 3​

Input: s = "(]"
Output: false

Example 4​

Input: s = "([])"
Output: true

🔑 Key Insights & Approach​

Core Observation: Use a stack to track opening brackets. When encountering closing bracket, check if it matches the most recent opening bracket.

Why Stack?

  • LIFO (Last In First Out) matches bracket nesting behavior
  • O(n) time complexity
  • O(n) space complexity
  • Perfect for matching problems

Approaches:

  1. Stack with matching logic: O(n) time, O(n) space - optimal

Pattern: "Stack for Matching/Validation" pattern - using stack for nested structures.

🐍 Solution: Python​

Approach: Stack with HashMap​

Time Complexity: O(n) | Space Complexity: O(n)

class Solution:
    def isValid(self, s: str) -> bool:
        # Mapping of closing to opening brackets
        bracket_map = {')': '(', '}': '{', ']': '['}
        stack = []

        for char in s:
            if char in bracket_map:
                # Closing bracket
                if not stack or stack[-1] != bracket_map[char]:
                    return False
                stack.pop()
            else:
                # Opening bracket
                stack.append(char)

        # Valid if stack is empty
        return len(stack) == 0

Approach 2: Explicit Checks​

Time Complexity: O(n) | Space Complexity: O(n)

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

        for char in s:
            if char in '({[':
                stack.append(char)
            else:
                if not stack:
                    return False

                top = stack.pop()
                if char == ')' and top != '(':
                    return False
                if char == '}' and top != '{':
                    return False
                if char == ']' and top != '[':
                    return False

        return len(stack) == 0

🔵 Solution: Golang​

Approach: Stack​

Time Complexity: O(n) | Space Complexity: O(n)

func isValid(s string) bool {
    // Map closing to opening brackets
    bracketMap := map[rune]rune{
        ')': '(',
        '}': '{',
        ']': '[',
    }

    stack := []rune{}

    for _, char := range s {
        if opening, isClosing := bracketMap[char]; isClosing {
            // Closing bracket
            if len(stack) == 0 || stack[len(stack)-1] != opening {
                return false
            }
            stack = stack[:len(stack)-1] // pop
        } else {
            // Opening bracket
            stack = append(stack, char)
        }
    }

    return len(stack) == 0
}

📚 References​