Watch 10 video solutions for Minimum Add to Make Parentheses Valid, a medium level problem involving String, Stack, Greedy. This walkthrough by Pepcoding has 9,270 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A parentheses string is valid if and only if:
AB (A concatenated with B), where A and B are valid strings, or(A), where A is a valid string.You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
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 ')'.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 | 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 |