Jobs

Interviews

Discussions

Generate Parentheses

Medium

Google

1 view

Topics:

Recursion

Given an integer n, write a function to generate all possible and valid combinations of parentheses, where n represents the number of pairs of parentheses.

Example 1:

Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Clarifications:

What should the function return if n is less than 1? (Clarify that n will always be greater or equal to 1 based on constraints).
What is the expected format of the output? (A list of strings, where each string is a valid combination of parentheses).
What constitutes a "valid" combination of parentheses? (Each open parenthesis must have a corresponding close parenthesis, and the close parenthesis must come after the open parenthesis).

Can you write an algorithm that efficiently generates all valid combinations of parentheses for a given n?

Generate Parentheses

Medium

Google

1 view

Topics:

Recursion

Given an integer n, write a function to generate all possible and valid combinations of parentheses, where n represents the number of pairs of parentheses.

Example 1:

Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Clarifications:

What should the function return if n is less than 1? (Clarify that n will always be greater or equal to 1 based on constraints).
What is the expected format of the output? (A list of strings, where each string is a valid combination of parentheses).
What constitutes a "valid" combination of parentheses? (Each open parenthesis must have a corresponding close parenthesis, and the close parenthesis must come after the open parenthesis).

Can you write an algorithm that efficiently generates all valid combinations of parentheses for a given n?

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:

What is the valid range for the input integer n? Is there a maximum value I should be aware of?
If n is 0, should I return an empty list or a list containing an empty string?
Is the order of the generated parenthesis combinations important? Should they be sorted in a specific way?
Do I need to handle any potential memory constraints given the number of combinations that could be generated for larger values of n?
Is there a specific format for the returned list of strings (e.g., can strings contain leading/trailing whitespace)?

Brute Force Solution

Approach

The brute force approach to generating parentheses is like trying every single combination of open and close parentheses until you find the valid ones. It's an exhaustive search where we explore all possibilities, regardless of whether they make sense at first.

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

Start by creating all possible strings of open and close parentheses with the given length.
For each of these strings, check if the parentheses are balanced and valid.
A string is considered valid if, for every close parenthesis, there is a matching open parenthesis before it, and the total number of open and close parentheses is correct.
If a string is valid, keep it; otherwise, discard it.
At the end, you will have a list of all valid combinations of parentheses.

Code Implementation

def generate_parentheses_brute_force(number):
    def generate_all_combinations(current_string, number):
        if len(current_string) == 2 * number:
            return [current_string]

        combinations = []
        combinations.extend(generate_all_combinations(current_string + '(', number))
        combinations.extend(generate_all_combinations(current_string + ')', number))
        return combinations

    def is_valid(parentheses_string):
        balance = 0
        for character in parentheses_string:
            if character == '(': 
                balance += 1
            else:
                balance -= 1
            
            # If balance goes below zero, it is invalid
            if balance < 0:
                return False

        # Check if balanced overall
        return balance == 0

    # Generate all possible combinations of parens
    all_combinations = generate_all_combinations("", number)
    
    valid_combinations = []
    # Filter out the invalid ones
    for combination in all_combinations:
        if is_valid(combination):
            valid_combinations.append(combination)
            
    return valid_combinations

Big(O) Analysis

Time Complexity

O(2^(2n) * n) – The brute force approach generates all possible strings of length 2n, where n is the number of open and close parentheses. There are 2 options (open or close) for each of the 2n positions, resulting in 2^(2n) possible strings. For each string, we must validate if it is a valid parentheses sequence, which takes O(n) time because we iterate through the entire string once. Therefore, the overall time complexity is O(2^(2n) * n).

Space Complexity

O(N) – The brute force approach generates all possible strings of parentheses, which are stored in memory. Each string has a length of 2N, where N is the input representing the number of pairs of parentheses. Although many strings are discarded, in the worst-case scenario, we could be storing a large number of these strings temporarily. Therefore, the auxiliary space complexity is proportional to the length of the strings generated, leading to O(N).

Optimal Solution

Approach

The best way to generate valid parentheses is to build them gradually, making sure we always have a balanced number of opening and closing parentheses. We add parentheses one at a time, carefully tracking how many opening parentheses we've used and how many we're allowed to use.

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

Imagine you're building a parentheses string, one character at a time.
Start with an empty string.
You're allowed to add an open parenthesis as long as you haven't used up all your available open parentheses.
You're allowed to add a close parenthesis only if you have more open parentheses in your string than close parentheses. This keeps things balanced.
Keep adding open and close parentheses, making sure to follow the rules above.
When you've used up all your open and close parentheses, the string is complete, and it's guaranteed to be valid.
Repeat this process, trying all possible combinations that follow the rules, until you've found them all.

Code Implementation

def generate_parentheses(number):
    results = []

    def backtrack(current_string, open_count, close_count):
        # When the string is complete, add to results.
        if len(current_string) == 2 * number:
            results.append(current_string)
            return

        # Add open parenthesis if we haven't used all.
        if open_count < number:
            backtrack(current_string + '(', open_count + 1, close_count)

        # Ensures that we are adding a valid closing parenthesis.
        if close_count < open_count:
            backtrack(current_string + ')', open_count, close_count + 1)

    # Initiate the process.
    backtrack('', 0, 0)
    return results

Big(O) Analysis

Time Complexity

O(4^n / sqrt(n)) – The algorithm generates all possible valid parentheses combinations using a recursive approach. The number of valid parentheses combinations grows exponentially. Specifically, it's related to the Catalan number, which is approximately 4^n / (n * sqrt(n)). Since each valid sequence has a length of 2n, and each step involves creating a new string, the time complexity to generate and store all sequences will be dominated by the number of valid parentheses. Therefore the time complexity is O(4^n / sqrt(n)).

Space Complexity

O(N) – The algorithm constructs valid parentheses strings using recursion. Each recursive call adds a new stack frame to the call stack. The maximum depth of the recursion is 2N, where N is the number of pairs of parentheses, as we add either an open or close parenthesis at each step until we have 2N parentheses. Additionally, we are building a string in each recursive call, which at maximum will also be of size 2N which is equivalent to N. Therefore, the auxiliary space complexity is dominated by the recursion depth and the string building, resulting in O(N).

Edge Cases

Case	How to Handle
n = 0	Return an empty list as there are no parentheses to generate.
n = 1	Return a list containing only '()'.
Very large n (e.g., n > 20)	The solution's time and space complexity should be exponential, so very large n may cause stack overflow or excessive memory usage, potentially requiring a check on the input value to prevent issues.
Negative n	Treat negative n as an invalid input and return an empty list or throw an exception.
Non-integer input	Ensure the input is an integer; otherwise, raise a TypeError or return an empty list if the input is invalid.
Recursion depth exceeding stack limit	For very large n, iterative solution can avoid stack overflow; else, optimize the recursive logic or use tail-call optimization if supported by the language.
n is a floating-point number	Convert the floating-point number to an integer using floor or round to ensure a valid input.
Memory constraints prevent storing all valid combinations	For extreme n, using a generator or streaming approach might mitigate memory overflow by not holding all combinations in memory at once.

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:

What is the valid range for the input integer n? Is there a maximum value I should be aware of?
If n is 0, should I return an empty list or a list containing an empty string?
Is the order of the generated parenthesis combinations important? Should they be sorted in a specific way?
Do I need to handle any potential memory constraints given the number of combinations that could be generated for larger values of n?
Is there a specific format for the returned list of strings (e.g., can strings contain leading/trailing whitespace)?

Brute Force Solution

Approach

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

Start by creating all possible strings of open and close parentheses with the given length.
For each of these strings, check if the parentheses are balanced and valid.
A string is considered valid if, for every close parenthesis, there is a matching open parenthesis before it, and the total number of open and close parentheses is correct.
If a string is valid, keep it; otherwise, discard it.
At the end, you will have a list of all valid combinations of parentheses.

Code Implementation

def generate_parentheses_brute_force(number):
    def generate_all_combinations(current_string, number):
        if len(current_string) == 2 * number:
            return [current_string]

        combinations = []
        combinations.extend(generate_all_combinations(current_string + '(', number))
        combinations.extend(generate_all_combinations(current_string + ')', number))
        return combinations

    def is_valid(parentheses_string):
        balance = 0
        for character in parentheses_string:
            if character == '(': 
                balance += 1
            else:
                balance -= 1
            
            # If balance goes below zero, it is invalid
            if balance < 0:
                return False

        # Check if balanced overall
        return balance == 0

    # Generate all possible combinations of parens
    all_combinations = generate_all_combinations("", number)
    
    valid_combinations = []
    # Filter out the invalid ones
    for combination in all_combinations:
        if is_valid(combination):
            valid_combinations.append(combination)
            
    return valid_combinations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you're building a parentheses string, one character at a time.
Start with an empty string.
You're allowed to add an open parenthesis as long as you haven't used up all your available open parentheses.
You're allowed to add a close parenthesis only if you have more open parentheses in your string than close parentheses. This keeps things balanced.
Keep adding open and close parentheses, making sure to follow the rules above.
When you've used up all your open and close parentheses, the string is complete, and it's guaranteed to be valid.
Repeat this process, trying all possible combinations that follow the rules, until you've found them all.

Code Implementation

def generate_parentheses(number):
    results = []

    def backtrack(current_string, open_count, close_count):
        # When the string is complete, add to results.
        if len(current_string) == 2 * number:
            results.append(current_string)
            return

        # Add open parenthesis if we haven't used all.
        if open_count < number:
            backtrack(current_string + '(', open_count + 1, close_count)

        # Ensures that we are adding a valid closing parenthesis.
        if close_count < open_count:
            backtrack(current_string + ')', open_count, close_count + 1)

    # Initiate the process.
    backtrack('', 0, 0)
    return results

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	Return an empty list as there are no parentheses to generate.
n = 1	Return a list containing only '()'.
Very large n (e.g., n > 20)	The solution's time and space complexity should be exponential, so very large n may cause stack overflow or excessive memory usage, potentially requiring a check on the input value to prevent issues.
Negative n	Treat negative n as an invalid input and return an empty list or throw an exception.
Non-integer input	Ensure the input is an integer; otherwise, raise a TypeError or return an empty list if the input is invalid.
Recursion depth exceeding stack limit	For very large n, iterative solution can avoid stack overflow; else, optimize the recursive logic or use tail-call optimization if supported by the language.
n is a floating-point number	Convert the floating-point number to an integer using floor or round to ensure a valid input.
Memory constraints prevent storing all valid combinations	For extreme n, using a generator or streaming approach might mitigate memory overflow by not holding all combinations in memory at once.