Jobs

Interviews

Discussions

Valid Parentheses

Easy

Netflix

0 views

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.

For example:

s = "()" should return true
s = "()[]{}" should return true
s = "(]" should return false
s = "([])" should return true
s = "([)]" should return false

Explain your approach to solve this problem. What data structures might be useful? What is the time and space complexity of your solution? Consider edge cases such as empty strings, strings with only one character, mismatched brackets, or strings with only opening or closing brackets.

Valid Parentheses

Easy

Netflix

0 views

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.

For example:

s = "()" should return true
s = "()[]{}" should return true
s = "(]" should return false
s = "([])" should return true
s = "([)]" should return false

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 the specified parentheses types ('(', ')', '{', '}', '[', ']') in the input string?
What is the maximum possible length of the input string `s`?
Should the order of mismatched brackets be considered when returning `false`, or is simply detecting an invalid string sufficient?
If the string contains only open brackets or only close brackets, what should the output be?

Brute Force Solution

Approach

The basic idea is to try removing matching parentheses until we can't anymore. If we end up with nothing, then it was valid. We repeatedly look for the simplest thing we can do to reduce the size of the problem.

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

Look through the entire input from beginning to end.
If you find an opening parenthesis followed immediately by its matching closing parenthesis, remove both of them.
Start back at the beginning and repeat the process.
Keep doing this until you can't find any more adjacent matching pairs to remove.
If, after all that removing, you're left with nothing, then the original input was valid. Otherwise, it was invalid.

Code Implementation

def is_valid_parentheses_brute_force(input_string):
    mutable_string = list(input_string)

    while True:
        found_match = False
        index = 0

        while index < len(mutable_string) - 1:
            # Need to check for pairs to remove

            if (mutable_string[index] == '(' and mutable_string[index + 1] == ')') or \
               (mutable_string[index] == '[' and mutable_string[index + 1] == ']') or \
               (mutable_string[index] == '{' and mutable_string[index + 1] == '}'):

                # Found a matching pair, so remove them
                mutable_string.pop(index + 1)
                mutable_string.pop(index)

                found_match = True

                # Reset index to start from the beginning
                index = 0
                continue

            index += 1

        # If no matches were found, exit the loop
        if not found_match:
            break

    # If the string is empty, it's valid
    return not mutable_string

Big(O) Analysis

Time Complexity

O(n²) – The described algorithm iterates through the input string of size n repeatedly. In the worst-case scenario, each iteration requires scanning the entire string to find and remove adjacent matching parentheses. Because we repeat the process until no more removals are possible, and in the worst case we remove only a single pair in each iteration, we might need to iterate up to n/2 times. Therefore, we have a nested loop situation where we scan the string of size n up to n/2 times, resulting in approximately n * n/2 operations, which simplifies to O(n²).

Space Complexity

O(N) – The plain English explanation implies repeated removals of adjacent matching parentheses from the input string. While not explicitly stated, this requires either modifying the original string in-place (potentially complex depending on the implementation) or, more likely, creating a modified copy of the string after each removal. The worst-case scenario occurs when there are no matching pairs initially, leading to creating copies of decreasing sizes until the final result, taking O(N) space. Thus, the auxiliary space is proportional to the input size, N, where N is the length of the input string. In the worst case, we might copy almost the entire string each time we remove a pair, requiring auxiliary space proportional to N.

Optimal Solution

Approach

The core idea is to use a special helper structure to keep track of opening parentheses. When we find a closing parenthesis, we check if it matches the last opening one we saw, and if so, remove the opening one. This efficiently tells us if the parentheses are balanced and correctly ordered.

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

Create a helper structure to remember the order of opening parentheses.
Go through the given parentheses one by one.
If you encounter an opening parenthesis, add it to the helper structure.
If you encounter a closing parenthesis, check if the helper structure is empty. If it is, this is invalid.
If the helper structure is not empty, compare the closing parenthesis to the last opening parenthesis in the helper structure.
If they match (e.g., '(' matches ')'), remove the opening parenthesis from the helper structure.
If they don't match, the string is invalid.
After processing all the parentheses, check if the helper structure is empty. If it is, the string is valid; otherwise, it's invalid because some opening parentheses were not closed.

Code Implementation

def is_valid(parentheses_string):
    parentheses_stack = []

    for parenthesis in parentheses_string:
        if parenthesis in ['(', '{', '[']:
            parentheses_stack.append(parenthesis)

        elif parenthesis in [')', '}', ']']:
            # Check for early closing parenthesis without an opening one.
            if not parentheses_stack:
                return False

            top_element = parentheses_stack.pop()

            # Verify the closing parenthesis matches the last opened one.
            if parenthesis == ')' and top_element != '(': 
                return False
            if parenthesis == '}' and top_element != '{':
                return False
            if parenthesis == ']' and top_element != '[':
                return False

    # Ensure all opened parentheses were properly closed.
    if not parentheses_stack:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n once. Inside the loop, the stack operations (push and pop) take constant time, O(1). The matching logic also takes constant time. Therefore, the time complexity is dominated by the single pass through the string, resulting in a time complexity of O(n).

Space Complexity

O(N) – The algorithm uses a helper structure (implicitly described as a 'pile') to store opening parentheses. In the worst-case scenario, the input string contains only opening parentheses, causing all of them to be added to the helper structure. Therefore, the space required by this helper structure grows linearly with the input size N, where N is the length of the input string. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return true immediately as an empty string is considered valid (no unmatched brackets).
String with only open brackets	The stack will not be empty at the end, resulting in a return of false.
String with only close brackets	The stack will be empty at the beginning, causing an attempt to pop from an empty stack or an early return of false.
String with mismatched bracket types, e.g., '({[}])'	When a closing bracket is encountered, the check against the top of the stack will fail the type comparison and return false.
String with incorrectly nested brackets, e.g., '[(])'	The order of brackets will cause a mismatch when attempting to close them off correctly based on their types, returning false.
String with an odd number of brackets, e.g., '((('	The stack will not be empty at the end, meaning not all brackets were closed correctly, returning false.
Very long input string (potential stack overflow with recursive solutions)	Use an iterative stack implementation to avoid potential stack overflow issues and ensure linear time complexity.
String contains non-bracket characters	The algorithm should gracefully ignore non-bracket characters as they do not affect validity.

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 the specified parentheses types ('(', ')', '{', '}', '[', ']') in the input string?
What is the maximum possible length of the input string `s`?
Should the order of mismatched brackets be considered when returning `false`, or is simply detecting an invalid string sufficient?
If the string contains only open brackets or only close brackets, what should the output be?

Brute Force Solution

Approach

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

Look through the entire input from beginning to end.
If you find an opening parenthesis followed immediately by its matching closing parenthesis, remove both of them.
Start back at the beginning and repeat the process.
Keep doing this until you can't find any more adjacent matching pairs to remove.
If, after all that removing, you're left with nothing, then the original input was valid. Otherwise, it was invalid.

Code Implementation

def is_valid_parentheses_brute_force(input_string):
    mutable_string = list(input_string)

    while True:
        found_match = False
        index = 0

        while index < len(mutable_string) - 1:
            # Need to check for pairs to remove

            if (mutable_string[index] == '(' and mutable_string[index + 1] == ')') or \
               (mutable_string[index] == '[' and mutable_string[index + 1] == ']') or \
               (mutable_string[index] == '{' and mutable_string[index + 1] == '}'):

                # Found a matching pair, so remove them
                mutable_string.pop(index + 1)
                mutable_string.pop(index)

                found_match = True

                # Reset index to start from the beginning
                index = 0
                continue

            index += 1

        # If no matches were found, exit the loop
        if not found_match:
            break

    # If the string is empty, it's valid
    return not mutable_string

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Create a helper structure to remember the order of opening parentheses.
Go through the given parentheses one by one.
If you encounter an opening parenthesis, add it to the helper structure.
If you encounter a closing parenthesis, check if the helper structure is empty. If it is, this is invalid.
If the helper structure is not empty, compare the closing parenthesis to the last opening parenthesis in the helper structure.
If they match (e.g., '(' matches ')'), remove the opening parenthesis from the helper structure.
If they don't match, the string is invalid.
After processing all the parentheses, check if the helper structure is empty. If it is, the string is valid; otherwise, it's invalid because some opening parentheses were not closed.

Code Implementation

def is_valid(parentheses_string):
    parentheses_stack = []

    for parenthesis in parentheses_string:
        if parenthesis in ['(', '{', '[']:
            parentheses_stack.append(parenthesis)

        elif parenthesis in [')', '}', ']']:
            # Check for early closing parenthesis without an opening one.
            if not parentheses_stack:
                return False

            top_element = parentheses_stack.pop()

            # Verify the closing parenthesis matches the last opened one.
            if parenthesis == ')' and top_element != '(': 
                return False
            if parenthesis == '}' and top_element != '{':
                return False
            if parenthesis == ']' and top_element != '[':
                return False

    # Ensure all opened parentheses were properly closed.
    if not parentheses_stack:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return true immediately as an empty string is considered valid (no unmatched brackets).
String with only open brackets	The stack will not be empty at the end, resulting in a return of false.
String with only close brackets	The stack will be empty at the beginning, causing an attempt to pop from an empty stack or an early return of false.
String with mismatched bracket types, e.g., '({[}])'	When a closing bracket is encountered, the check against the top of the stack will fail the type comparison and return false.
String with incorrectly nested brackets, e.g., '[(])'	The order of brackets will cause a mismatch when attempting to close them off correctly based on their types, returning false.
String with an odd number of brackets, e.g., '((('	The stack will not be empty at the end, meaning not all brackets were closed correctly, returning false.
Very long input string (potential stack overflow with recursive solutions)	Use an iterative stack implementation to avoid potential stack overflow issues and ensure linear time complexity.
String contains non-bracket characters	The algorithm should gracefully ignore non-bracket characters as they do not affect validity.