Minimum Add to Make Parentheses Valid - Solution & Explanation
Problem Statement
A parentheses string is valid if and only if:
- It is the empty string,
- It can be written as
AB(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis a valid string.
You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
- For example, if
s = "()))", you can insert an opening parenthesis to be"(()))"or a closing parenthesis to be"())))".
Return the minimum number of moves required to make s valid.
Example 1:
Input: s = "())" Output: 1
Example 2:
Input: s = "((("
Output: 3
Constraints:
1 <= s.length <= 1000s[i]is either'('or')'.
Approach Overview
Problem Overview: You get a string containing only '(' and ')'. The goal is to compute the minimum number of parentheses you must add so the final string becomes a valid parentheses sequence. A valid sequence means every opening parenthesis has a matching closing parenthesis and pairs appear in the correct order.
Approach 1: Greedy Balance Tracking (O(n) time, O(1) space)
This approach scans the string once while tracking a running balance of open parentheses. When you see '(', increment the balance because it expects a future closing bracket. When you see ')', decrement the balance. If the balance becomes negative, it means a closing parenthesis appeared without a matching opening one, so you must add an opening parenthesis and reset the balance to zero. After finishing the scan, any remaining positive balance represents unmatched opening parentheses, which require additional closing parentheses.
The key insight: every invalid ')' requires an inserted '(', and every leftover '(' requires a ')'. This greedy rule works because parentheses validity only depends on the running balance, not on rearranging characters. Time complexity is O(n) because you iterate once through the string, and space complexity is O(1) since only counters are stored. This method fits well with problems tagged under Greedy and String.
Approach 2: Stack Simulation (O(n) time, O(n) space)
This method explicitly simulates parentheses matching using a stack. Traverse the string character by character. Push every '(' onto the stack. When encountering ')', check the top of the stack: if an opening parenthesis exists, pop it to form a valid pair. If the stack is empty, the closing parenthesis has no match, so increment the required additions counter.
After processing the entire string, the stack may still contain unmatched opening parentheses. Each remaining element requires one closing parenthesis to make the string valid. The total additions equal the unmatched closing count plus the remaining stack size. This approach has O(n) time complexity because each character is processed once and stack operations are constant time. Space complexity is O(n) due to the stack storing unmatched parentheses. It mirrors the classic pattern used in many Stack problems.
Recommended for interviews: Greedy balance tracking is the expected solution. It achieves the same correctness as the stack simulation but reduces space from O(n) to O(1). Interviewers like to see the stack approach first because it demonstrates understanding of parentheses matching, then the greedy optimization that removes the extra memory.
Approach 1: Greedy Balance Tracking
This approach involves iterating through the string and using a balance counter to track the validity of the sequence.
We increment the balance for every opening parenthesis '(' and decrement it for a closing parenthesis ')'. If, at any point, the balance becomes negative, it means we have an extra closing parenthesis, and we need to increase the count of steps required to balance the string. By the end of the iteration, the balance will also tell us how many opening parentheses need to be closed to make the string valid.
The C implementation uses two variables, balance and result. We iterate over the string and adjust the balance for each parenthesis. Whenever balance is negative, it indicates an unmatched ')', and we increase the result to account for the needed '('. Finally, we return the sum of result and balance, where balance accounts for unmatched '('.
Complexity
Time Complexity: O(n) - We traverse the string once.
Space Complexity: O(1) - Only a few integer variables are used.
Approach 2: Stack Simulation
In this approach, we leverage a stack structure to simulate parentheses placement, assisting in counting the balance.
Iterate over the string, pushing opening parentheses onto the stack and popping for each encountered closing parenthesis when possible. When a closing parenthesis finds no partner to pop, increase the invalid count, simulating the need for one more opening parenthesis. In the end, the stack length represents unmatched opening parentheses.
Here, we maintain a stack variable to track open parentheses and an invalid count for unmatched closing parentheses. This eliminates the need for an actual stack structure, only integers are enough.
Complexity
Time Complexity: O(n) - Iterate over the string once.
Space Complexity: O(1) - Uses a few integer counters.
Approach 3: Greedy + Stack
This problem is a classic parenthesis matching problem, which can be solved using "Greedy + Stack".
Iterate through each character c in the string s:
- If
cis a left parenthesis, directly pushcinto the stack; - If
cis a right parenthesis, at this point if the stack is not empty, and the top element of the stack is a left parenthesis, then pop the top element of the stack, indicating a successful match; otherwise, pushcinto the stack.
After the iteration ends, the number of remaining elements in the stack is the number of parentheses that need to be added.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Greedy + Counting
Solution 1 uses a stack to implement parenthesis matching, but we can also directly implement it through counting.
Define a variable cnt to represent the current number of left parentheses to be matched, and a variable ans to record the answer. Initially, both variables are set to 0.
Iterate through each character c in the string s:
- If
cis a left parenthesis, increase the value ofcntby1; - If
cis a right parenthesis, at this point ifcnt > 0, it means that there are left parentheses that can be matched, so decrease the value ofcntby1; otherwise, it means that the current right parenthesis cannot be matched, so increase the value ofansby1.
After the iteration ends, add the value of cnt to ans, which is the answer.
The time complexity is O(n), and the space complexity is O(1), where n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
Approach 5: Replace + recursion
Code
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Balance Tracking | Time Complexity: O(n) - We traverse the string once. |
| Stack Simulation | Time Complexity: O(n) - Iterate over the string once. |
| Greedy + Stack | — |
| Greedy + Counting | — |
| Replace + recursion | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Balance Tracking | O(n) | O(1) | Best general solution when only the count of additions is required and memory efficiency matters |
| Stack Simulation | O(n) | O(n) | Useful for learning parentheses matching or when you need explicit tracking of unmatched characters |
Video Solution
Minimum Add to Make Parentheses Valid - Leetcode 921 - Python • NeetCodeIO • 9,555 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Add to Make Parentheses Valid easy or hard?
How to solve Minimum Add to Make Parentheses Valid in O(n)?
Minimum Add to Make Parentheses Valid Python or Java solution?
What is the best approach for Minimum Add to Make Parentheses Valid?
What data structure is used in Minimum Add to Make Parentheses Valid?
What is the time complexity of Minimum Add to Make Parentheses Valid?
Is Minimum Add to Make Parentheses Valid asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Minimum Add to Make Parentheses Valid with our built-in code editor and test cases.
Practice on FleetCode