Community Problem
Min Add to Make Parentheses Valid
Difficulty: Medium
Count the minimum number of '(' and ')' insertions that turn a parenthesis string valid using a single-pass two-counter scan.
Min Add to Make Parentheses Valid
Count the minimum number of '(' and ')' insertions that turn a parenthesis string valid using a single-pass two-counter scan.
By @kavyachakraborty
January 3, 2026
·
Updated May 18, 2026
1,200 views
27
4.6 (10)
This is a Series B onsite favorite because it tests whether a candidate reaches for a stack reflexively or notices the simpler counter pattern. I always pause and ask: do you actually need to know WHICH characters survive, or just HOW MANY of each kind to add? The latter is two integers and one pass.
Min Add to Make Parentheses Valid
A parenthesis string is valid if every '(' has a matching ')' to its right and every ')' has a matching '(' to its left. Given a string s consisting only of '(' and ')', return the minimum number of single-character insertions (of either '(' or ')') needed to make s valid.
Insertions can be made anywhere in the string. The original characters cannot be reordered or deleted.
Examples
Example 1:
- Input:
s = "())" - Output:
1 - Explanation: Insert one
'('to get"(())". One insertion suffices.
Example 2:
- Input:
s = "(((" - Output:
3 - Explanation: Insert three
')'to get"((()))".
Example 3:
- Input:
s = "()" - Output:
0 - Explanation: Already valid.
Example 4:
- Input:
s = "()))((" - Output:
4 - Explanation: Two
')'are unmatched on the left and two'('are unmatched on the right.
Constraints
1 <= s.length <= 1000s[i]is'('or')'.
Solution
Hints
Approach
A stack would also solve this, but we never need to know WHICH characters are unmatched, only HOW MANY are unmatched on each side. Two integers replace the stack cleanly.
Key insight
At the end of the scan there are two distinct kinds of unmatched characters: '(' that never found a ')' to their right (counted by open), and ')' that never had a '(' to their left (counted by addOpen, since these need an inserted '(' to fix). The sum is the minimum number of insertions.
Algorithm
- Initialize
open = 0(unmatched'('so far) andaddOpen = 0(number of')'we still owe a'('to). - For each character
chins:- If
ch == '(':open += 1. - Else: if
open > 0,open -= 1(cancel one pending opener); otherwiseaddOpen += 1(this')'is orphaned, we will need to insert a'('for it).
- Return
addOpen + open.
Complexity
Metric Value
------ -----
Time O(n)
Space O(1)A single linear pass with two integer counters; no auxiliary structure required.
Why it works
Greedy matching is optimal: every ')' should pair with the most recent unmatched '(' if one exists, since deferring the match never helps. After the scan, the remaining open counts '(' that still need a ')' appended; the addOpen counts ')' that need a '(' prepended. Both kinds are independent (any '(' we insert at the front does not steal from the '(' waiting at the end), so the answer is their sum.
Pitfalls
- Returning
Math.abs(net)wherenet = open - closeis wrong. The string"))(("has net 0 but needs 4 insertions. - Using a stack of characters works but is
O(n)space; the two-counter version is the cleaner expected answer. - Forgetting the post-loop
+ open. The orphaned closes are easy to count during the scan, but the orphaned opens only show up in the finalopenvalue.
Solution Code