Jobs

Interviews

Discussions

Valid Parentheses

Easy

Intuit

1 view

Topics:

StringsStacks

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

An input string is valid if:

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

Example 1:

Input: s = "()"

Output: true

Example 2:

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

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Example 5:

Input: s = "([)]"

Output: false

Constraints:

1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

Valid Parentheses

Easy

Intuit

1 view

Topics:

StringsStacks

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

An input string is valid if:

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

Example 1:

Input: s = "()"

Output: true

Example 2:

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

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Example 5:

Input: s = "([)]"

Output: false

Constraints:

1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be empty or null?
Are there any characters other than '(', ')', '{', '}', '[' and ']' in the input string?
Is there a maximum length for the input string `s`?
If the input string is invalid, are there specific criteria for determining why (e.g., mismatched brackets vs. incorrect order)? Although the return type is a boolean, understanding the failure modes may help structure the solution.
Should I assume the characters will always be valid UTF-8 characters?

Brute Force Solution

Approach

With the brute force method, we are trying to find if a string of parentheses is valid by generating and testing all combinations. We will explore every possible way the parentheses could be matched.

Here's how the algorithm would work step-by-step:

Start by checking if the string has an even number of parentheses. If it doesn't, it can't be valid.
Consider every possible arrangement of how the parentheses can be matched up.
For each possible arrangement, carefully go through the string, checking if each closing parenthesis has a matching opening parenthesis of the correct type (round, curly, square) before it.
If at any point you find a mismatch, that arrangement is invalid, and you discard it.
Continue testing each arrangement until you either find a valid one or exhaust all the possibilities.
If you find even one valid arrangement, the entire string is valid. If you exhaust all possibilities without finding a valid one, the string is invalid.

Code Implementation

def is_valid_parentheses_brute_force(input_string):
    string_length = len(input_string)

    # If the length is odd, it cannot be valid
    if string_length % 2 != 0:
        return False

    possible_arrangements = generate_arrangements(input_string)

    for arrangement in possible_arrangements:
        if is_valid_arrangement(arrangement):
            return True

    return False

def generate_arrangements(input_string):
    if not input_string:
        return [""]

    arrangements = []
    for i in range(len(input_string)):
        rest_of_string = input_string[:i] + input_string[i+1:]
        for sub_arrangement in generate_arrangements(rest_of_string):
            arrangements.append(input_string[i] + sub_arrangement)

    return arrangements

def is_valid_arrangement(arrangement):
    stack = []
    parentheses_map = {")": "(", "}": "{", "]": "["}

    for character in arrangement:
        if character in ['(', '{', '[']:
            stack.append(character)
        elif character in [')', '}', ']']:
            if not stack:
                return False
            top_element = stack.pop()

            # Check for matching parenthesis types
            if parentheses_map[character] != top_element:
                return False
    #The stack should be empty at the end
    return not stack

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O((2^n) * n) – The brute force approach generates all possible arrangements of parenthesis matching. The number of these arrangements grows exponentially with the number of parentheses, roughly as 2 raised to the power of n (where n is the number of parentheses), because each parenthesis has many potential matching options. For each arrangement, we iterate through the string (of length n) to validate whether the parentheses are correctly matched, requiring n operations. Therefore, the overall time complexity becomes O((2^n) * n).

Space Complexity

O(N!) – The brute force approach described involves generating all possible arrangements of parentheses matching. In the worst-case, where the input string 's' has length N (where N is the number of parentheses characters in the input string), creating each arrangement might require storing a modified string, or indices to track the arrangement. Generating all possible arrangements implies storing temporary data related to each arrangement. Generating all combinations involves factorials, therefore, the space used for storing/manipulating these combinations grows factorially with N, potentially leading to auxiliary space usage related to storing N! permutations. Even if not explicitly stored all at once, the implicit stack space used in recursion for generating these combinations can also be proportional to N!.

Optimal Solution

Approach

The best way to solve this is to use a mental model of cancelling things out. Think of opening parentheses as something that needs to be closed later. We use a mechanism to keep track of what needs to be closed.

Here's how the algorithm would work step-by-step:

Go through the string character by character.
If you see an opening parenthesis (like '(', '{', or '['), remember that you'll need to see the corresponding closing parenthesis later.
If you see a closing parenthesis, check if it matches the last opened parenthesis you were expecting.
If it matches, great! You've closed the last opened parenthesis, so you can forget about it.
If it doesn't match, or if you try to close a parenthesis when you haven't opened one, then the string is invalid.
At the end, if you've closed all the parentheses you opened, then the string is valid. If there are still open parentheses that haven't been closed, the string is invalid.

Code Implementation

def is_valid(string_of_parentheses: str) -> bool:
    stack_of_open_parentheses = []

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

    for character in string_of_parentheses:
        if character in parentheses_map.values():
            stack_of_open_parentheses.append(character)

        elif character in parentheses_map:
            # Need to check if there are any open parentheses
            if not stack_of_open_parentheses:
                return False

            # The top of the stack should match
            top_element = stack_of_open_parentheses.pop()

            if parentheses_map[character] != top_element:
                return False

    # At the end, the stack should be empty
    # to ensure proper opening and closing
    return not stack_of_open_parentheses

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once, examining each of the n characters. Inside the loop, the operations performed (checking if a character is an opening or closing parenthesis, matching parentheses, pushing/popping from the stack) take constant time, O(1). Therefore, the dominant factor is the single pass through the input string, resulting in a time complexity of O(n).

Space Complexity

O(N) – The provided solution uses a stack to keep track of opening parentheses. In the worst-case scenario, the input string contains only opening parentheses (e.g., '((((((('), which would all be added to the stack. Thus, the stack can grow up to the size of the input string, N, where N is the length of the input string. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty string	Return true, as an empty string is considered valid.
Null input	Return true, or throw an IllegalArgumentException depending on the specified requirements.
String with only open brackets (e.g., '{{{')	Return false, as there are unmatched open brackets.
String with only closing brackets (e.g., '}}}')	Return false, as there are no corresponding open brackets.
String with mismatched brackets (e.g., '({[}])')	Return false, because the brackets are not closed in the correct order.
String with mixed valid and invalid sequences (e.g., '(){}[](')	Return false, as the whole string must be validated.
Very long string, potentially exceeding stack size if using recursion.	Iterative solution using a stack avoids stack overflow issues for large inputs.
String containing characters other than brackets	Return false, or ignore the non-bracket characters, based on the specific requirements, while ensuring that the brackets are valid.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be empty or null?
Are there any characters other than '(', ')', '{', '}', '[' and ']' in the input string?
Is there a maximum length for the input string `s`?
If the input string is invalid, are there specific criteria for determining why (e.g., mismatched brackets vs. incorrect order)? Although the return type is a boolean, understanding the failure modes may help structure the solution.
Should I assume the characters will always be valid UTF-8 characters?

Brute Force Solution

Approach

With the brute force method, we are trying to find if a string of parentheses is valid by generating and testing all combinations. We will explore every possible way the parentheses could be matched.

Here's how the algorithm would work step-by-step:

Start by checking if the string has an even number of parentheses. If it doesn't, it can't be valid.
Consider every possible arrangement of how the parentheses can be matched up.
For each possible arrangement, carefully go through the string, checking if each closing parenthesis has a matching opening parenthesis of the correct type (round, curly, square) before it.
If at any point you find a mismatch, that arrangement is invalid, and you discard it.
Continue testing each arrangement until you either find a valid one or exhaust all the possibilities.
If you find even one valid arrangement, the entire string is valid. If you exhaust all possibilities without finding a valid one, the string is invalid.

Code Implementation

def is_valid_parentheses_brute_force(input_string):
    string_length = len(input_string)

    # If the length is odd, it cannot be valid
    if string_length % 2 != 0:
        return False

    possible_arrangements = generate_arrangements(input_string)

    for arrangement in possible_arrangements:
        if is_valid_arrangement(arrangement):
            return True

    return False

def generate_arrangements(input_string):
    if not input_string:
        return [""]

    arrangements = []
    for i in range(len(input_string)):
        rest_of_string = input_string[:i] + input_string[i+1:]
        for sub_arrangement in generate_arrangements(rest_of_string):
            arrangements.append(input_string[i] + sub_arrangement)

    return arrangements

def is_valid_arrangement(arrangement):
    stack = []
    parentheses_map = {")": "(", "}": "{", "]": "["}

    for character in arrangement:
        if character in ['(', '{', '[']:
            stack.append(character)
        elif character in [')', '}', ']']:
            if not stack:
                return False
            top_element = stack.pop()

            # Check for matching parenthesis types
            if parentheses_map[character] != top_element:
                return False
    #The stack should be empty at the end
    return not stack

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Go through the string character by character.
If you see an opening parenthesis (like '(', '{', or '['), remember that you'll need to see the corresponding closing parenthesis later.
If you see a closing parenthesis, check if it matches the last opened parenthesis you were expecting.
If it matches, great! You've closed the last opened parenthesis, so you can forget about it.
If it doesn't match, or if you try to close a parenthesis when you haven't opened one, then the string is invalid.
At the end, if you've closed all the parentheses you opened, then the string is valid. If there are still open parentheses that haven't been closed, the string is invalid.

Code Implementation

def is_valid(string_of_parentheses: str) -> bool:
    stack_of_open_parentheses = []

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

    for character in string_of_parentheses:
        if character in parentheses_map.values():
            stack_of_open_parentheses.append(character)

        elif character in parentheses_map:
            # Need to check if there are any open parentheses
            if not stack_of_open_parentheses:
                return False

            # The top of the stack should match
            top_element = stack_of_open_parentheses.pop()

            if parentheses_map[character] != top_element:
                return False

    # At the end, the stack should be empty
    # to ensure proper opening and closing
    return not stack_of_open_parentheses

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string	Return true, as an empty string is considered valid.
Null input	Return true, or throw an IllegalArgumentException depending on the specified requirements.
String with only open brackets (e.g., '{{{')	Return false, as there are unmatched open brackets.
String with only closing brackets (e.g., '}}}')	Return false, as there are no corresponding open brackets.
String with mismatched brackets (e.g., '({[}])')	Return false, because the brackets are not closed in the correct order.
String with mixed valid and invalid sequences (e.g., '(){}[](')	Return false, as the whole string must be validated.
Very long string, potentially exceeding stack size if using recursion.	Iterative solution using a stack avoids stack overflow issues for large inputs.
String containing characters other than brackets	Return false, or ignore the non-bracket characters, based on the specific requirements, while ensuring that the brackets are valid.