Jobs

Interviews

Discussions

Generate Parentheses

#2 Most AskedMedium

Generate Parentheses #2 Most Asked

Medium

Veeva Systems

27 views

Topics:

StringsRecursionBacktracking

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

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

Example 2:

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

Constraints:

1 <= n <= 8

Try coding it in LeetCode

Generate Parentheses

#2 Most AskedMedium

Generate Parentheses #2 Most Asked

Medium

Veeva Systems

27 views

Topics:

StringsRecursionBacktracking

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

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

Example 2:

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

Constraints:

1 <= n <= 8

Try coding it in LeetCode

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 are the constraints on the input integer 'n'? For example, can 'n' be 0 or negative?
Are there any specific ordering requirements for the generated valid parenthesis combinations in the output list?
If 'n' is 0, what should the function return?
Is it possible for the input 'n' to be extremely large, and if so, should I be concerned about memory or time complexity beyond a standard optimal solution?
Could you provide an example for 'n' = 3 to illustrate the expected output format and the definition of 'well-formed'?

Brute Force Solution

Approach

The brute force approach to generating valid parentheses involves creating every possible combination of opening and closing parentheses and then checking each one to see if it's valid. It's like trying out every single arrangement of building blocks before finding the ones that form a stable structure.

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

First, imagine you have a set number of opening and closing parentheses to work with.
Generate every single way you can arrange these parentheses, without worrying if they make sense yet.
For each of these arrangements, examine it carefully to see if it follows the rules of valid parentheses.
The rules are simple: you can never have more closing parentheses than opening ones at any point, and in the end, the total number of opening and closing parentheses must be equal.
If an arrangement follows all these rules, keep it.
Discard any arrangement that breaks the rules.
The collection of all the arrangements you kept is your final answer.

Code Implementation

def generate_parenthesis_brute_force(number_of_pairs):
    all_parentheses_combinations = []
    final_valid_parentheses = []
    
    def generate_all_combinations(current_combination):
        if len(current_combination) == 2 * number_of_pairs:
            all_parentheses_combinations.append("".join(current_combination))
            return
        
        current_combination.append('(')
        generate_all_combinations(current_combination)
        current_combination.pop()
        
        current_combination.append(')')
        generate_all_combinations(current_combination)
        current_combination.pop()

    def is_valid_parentheses(parentheses_string):
        balance_counter = 0
        # This check ensures we never have more closing than opening parentheses at any point.
        for character in parentheses_string:
            if character == '(':
                balance_counter += 1
            else:
                balance_counter -= 1
            
            if balance_counter < 0:
                return False
        
        # This check ensures that the total number of opening and closing parentheses are equal.
        return balance_counter == 0

    generate_all_combinations([])

    # Iterate through all generated combinations to filter out invalid ones.
    for combination in all_parentheses_combinations:
        if is_valid_parentheses(combination):
            final_valid_parentheses.append(combination)

    return final_valid_parentheses

Big(O) Analysis

Time Complexity

O(n * 4^n / sqrt(n)) – The brute force approach generates all possible combinations of parentheses. For n pairs of parentheses, there are 2n positions. The number of ways to place n opening parentheses in 2n positions is given by the binomial coefficient C(2n, n). Each generated string needs to be validated, which takes O(n) time. The number of valid parentheses strings for n pairs is given by the nth Catalan number, which is C(2n, n) / (n+1). However, the brute force generates all 2^(2n) strings and then filters. The generation of all 2^(2n) combinations is the dominant factor. Thus, the time complexity is approximately O(2^(2n) * n), which can be simplified to O(n * 4^n / sqrt(n)).

Space Complexity

O(n) – The primary auxiliary space usage comes from storing the generated valid parentheses strings. Since there can be up to Catalan(n) valid combinations, and each string has length 2n, the space complexity is dominated by the storage of these results. The recursive calls themselves, if a backtracking approach is used to generate these, contribute to the call stack depth, which can be at most O(n). Therefore, the auxiliary space complexity is O(n) due to the output storage and recursion depth.

Optimal Solution

Approach

This problem is about building valid arrangements of parentheses. The best way to do this is to think about it as a process of making choices step by step, ensuring that at each point, the choices we make are valid and lead us towards a complete, correct arrangement.

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

Imagine you're building a sequence of parentheses, one character at a time.
At any point, you can either add an opening parenthesis or a closing parenthesis.
However, you can only add an opening parenthesis if you haven't used up all the allowed opening parentheses yet.
You can only add a closing parenthesis if there's a matching opening parenthesis that hasn't been closed yet.
Keep track of how many opening parentheses you've used and how many closing parentheses you've used.
When you've used exactly the total number of opening parentheses and the total number of closing parentheses, you've found a valid arrangement.
Explore all possible valid paths of adding parentheses until you've found every single valid arrangement.
This systematic exploration, making valid choices at each step, ensures you generate all possibilities without creating invalid ones.

Code Implementation

def generate_parenthesis_combinations(maximum_pairs):
    all_valid_combinations = []

    def backtrack_parentheses(current_string, open_count, close_count):
        # Base case: If the current string is complete, add it to results.
        if len(current_string) == maximum_pairs * 2:
            all_valid_combinations.append(current_string)
            return

        # Rule: Can add an opening parenthesis if we haven't used all available.
        if open_count < maximum_pairs:
            backtrack_parentheses(current_string + '(', open_count + 1, close_count)

        # Rule: Can add a closing parenthesis if it matches an open one.
        if close_count < open_count:
            backtrack_parentheses(current_string + ')', open_count, close_count + 1)

    backtrack_parentheses('', 0, 0)
    return all_valid_combinations

Big(O) Analysis

Time Complexity

O(4^n / (n * sqrt(n))) – The problem is solved using recursion (backtracking) where at each step, we have at most two choices: adding an opening parenthesis or a closing parenthesis. The depth of the recursion is 2n (since we add 2n parentheses in total). The number of valid parentheses combinations grows according to the Catalan numbers, which can be approximated by 4^n / (n * sqrt(n)). Each recursive call performs constant time operations (checks and appends). Therefore, the total time complexity is proportional to the number of valid combinations.

Space Complexity

O(n) – The primary auxiliary space is consumed by the recursion stack. At any point, the depth of the recursion can go up to 2*n, representing the maximum length of a valid parenthesis string. Additionally, a list is used to store all generated valid parenthesis strings. If 'n' represents the number of pairs of parentheses, the number of valid combinations grows catalan(n), which is exponential. However, the space complexity for the recursion stack and the temporary string being built at any given recursion level is O(n). The final output storage is not typically counted as auxiliary space unless explicitly stated. Therefore, the dominant auxiliary space complexity is driven by the recursion depth and the temporary string construction, resulting in O(n).

Edge Cases

Case	How to Handle
n = 0 (zero pairs of parentheses)	The algorithm should return a list containing a single empty string, representing no parentheses.
n = 1 (one pair of parentheses)	The algorithm should correctly generate and return a list containing only '()'.
Large values of n	For very large n, the number of combinations grows exponentially, potentially leading to performance issues (time complexity) and memory constraints. The recursive backtracking approach is generally efficient for reasonable n.
Negative input for n	The problem statement implies n is a non-negative integer; a negative n should ideally result in an empty list or an error, as it's an invalid input for the number of pairs.
Non-integer input for n	The problem specifies an integer n; non-integer inputs are out of scope and should be handled by input validation if necessary.
Maximum recursion depth exceeded for very large n	If n is extremely large, a recursive solution might hit the maximum recursion depth limit of the language, requiring an iterative approach or increasing the recursion limit if feasible.
No valid combinations exist (though not possible for n >= 0)	For n >= 0, there will always be at least one valid combination (the empty string for n=0) or multiple combinations for n > 0.
Multiple valid solutions are possible	The core requirement of the problem is to generate ALL valid combinations, so the algorithm must be designed to explore all valid paths to produce them.

n = 0 (zero pairs of parentheses)

How to Handle:

The algorithm should return a list containing a single empty string, representing no parentheses.

n = 1 (one pair of parentheses)

How to Handle:

The algorithm should correctly generate and return a list containing only '()'.

Large values of n

How to Handle:

For very large n, the number of combinations grows exponentially, potentially leading to performance issues (time complexity) and memory constraints. The recursive backtracking approach is generally efficient for reasonable n.

Negative input for n

How to Handle:

The problem statement implies n is a non-negative integer; a negative n should ideally result in an empty list or an error, as it's an invalid input for the number of pairs.

Non-integer input for n

How to Handle:

The problem specifies an integer n; non-integer inputs are out of scope and should be handled by input validation if necessary.

Maximum recursion depth exceeded for very large n

How to Handle:

If n is extremely large, a recursive solution might hit the maximum recursion depth limit of the language, requiring an iterative approach or increasing the recursion limit if feasible.

No valid combinations exist (though not possible for n >= 0)

How to Handle:

For n >= 0, there will always be at least one valid combination (the empty string for n=0) or multiple combinations for n > 0.

Multiple valid solutions are possible

How to Handle:

The core requirement of the problem is to generate ALL valid combinations, so the algorithm must be designed to explore all valid paths to produce them.

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 are the constraints on the input integer 'n'? For example, can 'n' be 0 or negative?
Are there any specific ordering requirements for the generated valid parenthesis combinations in the output list?
If 'n' is 0, what should the function return?
Is it possible for the input 'n' to be extremely large, and if so, should I be concerned about memory or time complexity beyond a standard optimal solution?
Could you provide an example for 'n' = 3 to illustrate the expected output format and the definition of 'well-formed'?

Brute Force Solution

Approach

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

First, imagine you have a set number of opening and closing parentheses to work with.
Generate every single way you can arrange these parentheses, without worrying if they make sense yet.
For each of these arrangements, examine it carefully to see if it follows the rules of valid parentheses.
The rules are simple: you can never have more closing parentheses than opening ones at any point, and in the end, the total number of opening and closing parentheses must be equal.
If an arrangement follows all these rules, keep it.
Discard any arrangement that breaks the rules.
The collection of all the arrangements you kept is your final answer.

Code Implementation

def generate_parenthesis_brute_force(number_of_pairs):
    all_parentheses_combinations = []
    final_valid_parentheses = []
    
    def generate_all_combinations(current_combination):
        if len(current_combination) == 2 * number_of_pairs:
            all_parentheses_combinations.append("".join(current_combination))
            return
        
        current_combination.append('(')
        generate_all_combinations(current_combination)
        current_combination.pop()
        
        current_combination.append(')')
        generate_all_combinations(current_combination)
        current_combination.pop()

    def is_valid_parentheses(parentheses_string):
        balance_counter = 0
        # This check ensures we never have more closing than opening parentheses at any point.
        for character in parentheses_string:
            if character == '(':
                balance_counter += 1
            else:
                balance_counter -= 1
            
            if balance_counter < 0:
                return False
        
        # This check ensures that the total number of opening and closing parentheses are equal.
        return balance_counter == 0

    generate_all_combinations([])

    # Iterate through all generated combinations to filter out invalid ones.
    for combination in all_parentheses_combinations:
        if is_valid_parentheses(combination):
            final_valid_parentheses.append(combination)

    return final_valid_parentheses

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 sequence of parentheses, one character at a time.
At any point, you can either add an opening parenthesis or a closing parenthesis.
However, you can only add an opening parenthesis if you haven't used up all the allowed opening parentheses yet.
You can only add a closing parenthesis if there's a matching opening parenthesis that hasn't been closed yet.
Keep track of how many opening parentheses you've used and how many closing parentheses you've used.
When you've used exactly the total number of opening parentheses and the total number of closing parentheses, you've found a valid arrangement.
Explore all possible valid paths of adding parentheses until you've found every single valid arrangement.
This systematic exploration, making valid choices at each step, ensures you generate all possibilities without creating invalid ones.

Code Implementation

def generate_parenthesis_combinations(maximum_pairs):
    all_valid_combinations = []

    def backtrack_parentheses(current_string, open_count, close_count):
        # Base case: If the current string is complete, add it to results.
        if len(current_string) == maximum_pairs * 2:
            all_valid_combinations.append(current_string)
            return

        # Rule: Can add an opening parenthesis if we haven't used all available.
        if open_count < maximum_pairs:
            backtrack_parentheses(current_string + '(', open_count + 1, close_count)

        # Rule: Can add a closing parenthesis if it matches an open one.
        if close_count < open_count:
            backtrack_parentheses(current_string + ')', open_count, close_count + 1)

    backtrack_parentheses('', 0, 0)
    return all_valid_combinations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0 (zero pairs of parentheses)	The algorithm should return a list containing a single empty string, representing no parentheses.
n = 1 (one pair of parentheses)	The algorithm should correctly generate and return a list containing only '()'.
Large values of n	For very large n, the number of combinations grows exponentially, potentially leading to performance issues (time complexity) and memory constraints. The recursive backtracking approach is generally efficient for reasonable n.
Negative input for n	The problem statement implies n is a non-negative integer; a negative n should ideally result in an empty list or an error, as it's an invalid input for the number of pairs.
Non-integer input for n	The problem specifies an integer n; non-integer inputs are out of scope and should be handled by input validation if necessary.
Maximum recursion depth exceeded for very large n	If n is extremely large, a recursive solution might hit the maximum recursion depth limit of the language, requiring an iterative approach or increasing the recursion limit if feasible.
No valid combinations exist (though not possible for n >= 0)	For n >= 0, there will always be at least one valid combination (the empty string for n=0) or multiple combinations for n > 0.
Multiple valid solutions are possible	The core requirement of the problem is to generate ALL valid combinations, so the algorithm must be designed to explore all valid paths to produce them.

n = 0 (zero pairs of parentheses)

How to Handle:

The algorithm should return a list containing a single empty string, representing no parentheses.

n = 1 (one pair of parentheses)

How to Handle:

The algorithm should correctly generate and return a list containing only '()'.

Large values of n

How to Handle:

Negative input for n

How to Handle:

The problem statement implies n is a non-negative integer; a negative n should ideally result in an empty list or an error, as it's an invalid input for the number of pairs.

Non-integer input for n

How to Handle:

The problem specifies an integer n; non-integer inputs are out of scope and should be handled by input validation if necessary.

Maximum recursion depth exceeded for very large n

How to Handle:

If n is extremely large, a recursive solution might hit the maximum recursion depth limit of the language, requiring an iterative approach or increasing the recursion limit if feasible.

No valid combinations exist (though not possible for n >= 0)

How to Handle:

For n >= 0, there will always be at least one valid combination (the empty string for n=0) or multiple combinations for n > 0.

Multiple valid solutions are possible

How to Handle:

The core requirement of the problem is to generate ALL valid combinations, so the algorithm must be designed to explore all valid paths to produce them.

0/4 Veeva Systems questions completed

0/4 completed