How do you solve Minimum Add to Make Parentheses Valid on LeetCode?

Minimum Add to Make Parentheses Valid (LeetCode #921) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding how to balance parentheses is crucial for solving similar problems.

What is the brute force solution for Minimum Add to Make Parentheses Valid?

The brute force approach for Minimum Add to Make Parentheses Valid is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible valid parentheses combinations by inserting parentheses at various positions. We then check which combination is valid and count the number of insertions needed. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Minimum Add to Make Parentheses Valid?

Minimum Add to Make Parentheses Valid uses the following concepts: String, Stack, Greedy. The recommended patterns to study are: Greedy, Stack.

What are the interview tips for Minimum Add to Make Parentheses Valid?

Always consider edge cases, such as strings that are already valid or completely invalid. Explain your thought process clearly; it helps the interviewer understand your approach. Practice similar problems to recognize patterns in parentheses balancing.

What are common mistakes when solving Minimum Add to Make Parentheses Valid?

Failing to account for unmatched closing parentheses. Overcomplicating the solution by trying to generate all combinations.

#921

Minimum Add to Make Parentheses Valid

Medium

StringStackGreedyGreedyStack

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses a greedy approach to count the number of unmatched opening and closing parentheses. By keeping track of these counts, we can determine the minimum number of insertions needed to balance the string.

⚙️

Algorithm

4 steps

1Step 1: Initialize two counters: one for unmatched opening parentheses and one for unmatched closing parentheses.
2Step 2: Iterate through each character in the string.
3Step 3: If the character is '(', increment the unmatched opening counter. If it is ')', check if there is an unmatched opening to pair with; if so, decrement the unmatched opening counter, otherwise increment the unmatched closing counter.
4Step 4: The result is the sum of unmatched opening and closing counters.

solution.py12 lines

1def minAddToMakeValid(s):
2    open_count = 0
3    close_count = 0
4    for char in s:
5        if char == '(': open_count += 1
6        else:
7            if open_count > 0:
8                open_count -= 1
9            else:
10                close_count += 1
11    return open_count + close_count
12

ℹ

Complexity note: The time complexity is O(n) because we only make a single pass through the string, counting unmatched parentheses. The space complexity is O(1) since we only use a fixed number of counters.

1Understanding how to balance parentheses is crucial for solving similar problems.
2Using counters to track unmatched parentheses can simplify the problem significantly.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.