Minimum Add to Make Parentheses Valid: One Greedy Pass
Solve Minimum Add to Make Parentheses Valid in one greedy pass — track two deficits, add them, done. Intuition, JavaScript code, a worked trace, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Balancing parentheses looks like it should need a stack — push openers, pop on close, count the leftovers. It doesn't. This problem collapses into two integers you carry left to right, and the answer is their sum.
The trick is realizing you never need to store the brackets, only count two kinds of debt: openers still waiting for a close, and closers that arrived with no opener to match. That reframe turns an intimidating string problem into eight lines of arithmetic.
The problem
Given a string s of only ( and ), return the minimum number of parentheses you must insert — anywhere in the string — so that every bracket is matched and the whole thing is valid.
A string is valid when every ( has a later ) partner and every ) has an earlier ( partner, properly nested.
Input: s = "())("
Output: 2 // add one '(' before index 2, and one ')' at the endTwo facts shape the solution:
- You may insert anywhere, so an orphaned
)is always fixable by prepending a(, and a leftover(is always fixable by appending a). No arrangement is ever impossible. - You want the minimum count, so you must match greedily and only pay for brackets that genuinely have no partner.
The brute force baseline
The instinct is to simulate matching with a stack: push every (, and on each ) pop a waiting opener if one exists.
function minAddToMakeValid(s) {
const stack = [];
let unmatchedClose = 0;
for (const char of s) {
if (char === "(") {
stack.push(char);
} else {
if (stack.length > 0) stack.pop();
else unmatchedClose++;
}
}
return stack.length + unmatchedClose;
}This is actually correct and runs in O(n) time. The waste is space: the stack holds every unmatched ( even though you never inspect which opener it is — you only ever ask "is one available?" and "how many are left?" A stack of identical ( characters is a counter wearing a costume. That observation is the whole optimization.
The key insight: two deficits, not a stack
Replace the stack with a single integer, leftUnmatched, that counts how many ( are currently waiting for a partner. A second integer, rightNeeded, counts orphaned ) that showed up with nothing to match.
Walk the string once:
- On
(: incrementleftUnmatched— a new promise that a)must follow. - On
): ifleftUnmatched > 0, a waiting opener exists, so consume it (leftUnmatched--). Otherwise this)is orphaned, sorightNeeded++.
Why is matching immediately always safe? Because parentheses nest strictly. A ) can only ever pair with the most recent unmatched (, so pairing the moment you can never blocks a better future pairing — there is no better one. That is what makes the greedy pass optimal.
At the end, leftUnmatched openers each need a ) appended, and rightNeeded closers each need a ( prepended. The answer is simply their sum.
The optimal solution
var minAddToMakeValid = function (s) {
let leftUnmatched = 0;
let rightNeeded = 0;
for (let char of s) {
if (char === "(") {
leftUnmatched++;
} else if (char === ")") {
if (leftUnmatched > 0) {
leftUnmatched--;
} else {
rightNeeded++;
}
}
}
return leftUnmatched + rightNeeded;
};leftUnmatched never goes negative because the else branch catches every ) that has no opener and diverts it to rightNeeded instead. Those two counters never interfere: one measures missing closers, the other measures missing openers, and both are pure insertions you'll have to make.
Walkthrough
Trace s = "())(". Watch how the two counters diverge — leftUnmatched rises and falls, rightNeeded only ever rises.
| Step | index | char | leftUnmatched | rightNeeded | What happened |
|---|---|---|---|---|---|
| 0 | — | init | 0 | 0 | Both counters start at zero |
| 1 | 0 | ( | 1 | 0 | New opener waiting for a close |
| 2 | 1 | ) | 0 | 0 | leftUnmatched > 0, so match and consume it |
| 3 | 2 | ) | 0 | 1 | No opener available → orphaned close |
| 4 | 3 | ( | 1 | 0... | New opener waiting; rightNeeded stays 1 |
Final state: leftUnmatched = 1, rightNeeded = 1, so the answer is 1 + 1 = 2. Step 3 is the important one — the ) at index 2 finds leftUnmatched already at zero, so it can't match and instead demands a ( be inserted before it. Meanwhile the ( at index 3 ends the pass still waiting, demanding a ) after it.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Stack simulation | O(n) | O(n) | stack holds up to n unmatched openers |
| Two counters | O(n) | O(1) | one pass, two integers, constant memory |
Both do a single linear scan, so time is identical. The counter version wins on space: it never allocates anything that grows with input length. On a 10⁵-character string the stack version can hold 10⁵ entries; the counter version holds two.
Common mistakes
- Letting the open counter go negative. If you write
leftUnmatched--unconditionally on every), a string like))drives it to-2and you lose the count of orphaned closers entirely. Theif (leftUnmatched > 0)guard is load-bearing. - Trying to return early. There is no early exit — you must scan the entire string, because a leftover
(at the very end still contributes to the answer. - Counting positions instead of deficits. You don't need the indices of unmatched brackets, only how many there are. Storing indices is extra work that never affects the result.
- Assuming the string is only brackets and skipping the guard. This specific problem guarantees only
(and), but theelse if (char === ")")check keeps the logic correct if other characters ever appear — they're simply ignored.
Where this pattern shows up next
The "scan once, carry a running count, ignore the structure you don't need" idea powers a lot of string work:
- Reverse Words in a String — single-pass parsing where you track word boundaries instead of bracket debt.
- Decode String — the stack version of bracket handling, for when nesting does carry information you must keep.
- Sum of Beauty of All Substrings — counting frequencies in a rolling window rather than storing the substring.
- Count and Say — run-length counting during a linear scan of a string.
You can also step through this problem interactively to watch the two counters rise and fall character by character.
FAQ
Why does this problem not need a stack?
A stack would store every unmatched (, but you never look at which opener sits there — only whether one is available and how many remain. Both questions are answered by a single integer counter. Since parentheses of one type carry no identity, the stack degenerates into a count, and you can replace it with a plain variable for O(1) space.
Why is the greedy match always optimal?
Because parentheses nest strictly, a ) can only ever pair with the nearest preceding unmatched (. There is never a "better" opener to save it for. Matching the instant an opener is available therefore never costs you a future opportunity, so the locally optimal choice is also globally optimal — the defining property of a valid greedy solution.
What do the two counters actually represent?
leftUnmatched is the number of ( that finished the scan still waiting for a partner; each needs a ) appended. rightNeeded is the number of ) that arrived with no opener available; each needs a ( prepended. They measure two independent kinds of insertion, which is why the answer is simply their sum and never a max or a difference.
What is the time and space complexity?
O(n) time and O(1) space. The string is scanned exactly once, doing constant work per character — a comparison and one increment or decrement. Unlike the stack approach, no auxiliary structure grows with the input, so memory stays flat at two integers regardless of string length.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.