Minimum Add to Make Parentheses Valid Solution

Problem

Given a string containing only ( and ) characters, return the minimum number of parentheses you must insert — anywhere in the string — to make it valid. A string is valid when every opening bracket has a matching closing bracket, and every closing bracket has a matching opening bracket to its left.

Example:

Input: s = "())(("
Output: 3
Explanation: There is one unmatched ) that needs a ( added before it, and two unmatched ( that each need a ) added after them.

Counter-example: "(())" needs 0 insertions because every bracket has a match; ")(" needs 2 insertions even though the character count is balanced, because the ) comes before the (.

Intuition

Walk through the string once and count how many brackets are "stranded." A ) is stranded when there is no earlier unmatched ( to pair with; a ( is stranded when it reaches the end of the string without a ). The answer is the total number of stranded brackets, because each one requires exactly one insertion to match it.

Approach 1 — Stack

Use a stack to explicitly track unmatched ( characters as you scan left to right. When you see a ), pop from the stack if possible (a match was found); otherwise increment a counter for unmatched ). At the end, the stack holds all unmatched (.

Initialize an empty stack and a counter open_needed = 0.
For each character in the string:
- If (, push it onto the stack.
- If ), pop from the stack if it is non-empty (a match). Otherwise increment open_needed.
Return open_needed + len(stack).

1def minAddToMakeValid(s: str) -> int:
2    stack = []
3    open_needed = 0  # count of ')' with no matching '(' to their left
4
5    for char in s:
6        if char == '(':
7            stack.append(char)
8        else:
9            if stack:
10                stack.pop()  # this ')' matches the most recent unmatched '('
11            else:
12                open_needed += 1  # no '(' available; must insert one
13    
14    return open_needed + len(stack)  # len(stack) = count of unmatched '('

Time: O(n) — one pass through the string.
Space: O(n) — the stack can hold up to n characters in the worst case (e.g. "((((").

Approach 2 — Two Counters (Optimal Space)

Since we only need counts and not positions, replace the stack with two integer counters: open_needed for unmatched ) and close_needed for unmatched (. This eliminates the stack entirely.

Initialize open_needed = 0 and close_needed = 0.
For each character:
- If (, increment close_needed (this ( is waiting for a future )).
- If ), decrement close_needed if it is positive (a match was found). Otherwise increment open_needed (need to insert a ().
Return open_needed + close_needed.

1def minAddToMakeValid(s: str) -> int:
2    open_needed = 0   # unmatched ')' seen so far — need a '(' inserted before each
3    close_needed = 0  # unmatched '(' seen so far — need a ')' inserted after each
4
5    for char in s:
6        if char == '(':
7            close_needed += 1  # this '(' is waiting for a future ')'
8        else:
9            if close_needed > 0:
10                close_needed -= 1  # matched with the most recent unmatched '('
11            else:
12                open_needed += 1   # no '(' to match; must insert one before this ')'
13
14    return open_needed + close_needed

Time: O(n) — one pass through the string.
Space: O(1) — only two integer counters regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Stack	O(n)	O(n)	When you need to know the actual positions of unmatched brackets, not just the count
Two Counters	O(n)	O(1)	Default choice — only the minimum count is needed

Common Mistakes

Checking abs(opens - closes) as the answer: ")(" has one ( and one ), so abs(1 - 1) = 0, but the correct answer is 2. Order matters — the ) comes before the ( with no way to match it.
Forgetting to handle both directions of imbalance: Some solutions only count unmatched ) and miss unmatched ( at the end. You need both open_needed (for stranded )) and close_needed (for stranded ().
Decrementing close_needed below zero: When seeing a ) with no unmatched ( to pair with, decrementing instead of clamping would make future matches incorrect. Guard the decrement with if close_needed > 0.
Using net = opens - closes then returning abs(net): This fails on inputs like ")))(((" where the imbalance is in both directions. net would be 0 but the correct answer is 6.
Confusing which counter tracks which bracket type: open_needed counts how many ( you need to add, triggered by seeing an unmatched ). close_needed counts how many ) you need to add, triggered by seeing an unmatched (. The names refer to what is needed, not what was seen.

Minimum Add to Make Parentheses Valid — Solution