Minimum Add to Make Parentheses Valid: Greedy Balance Counting

Given a parentheses string s containing only '(' and ')', return the minimum number of parentheses you must add to make the string valid. A string is valid if every open parenthesis has a corresponding close parenthesis in the correct order.

This is LeetCode 921: Minimum Add to Make Parentheses Valid, a medium problem that looks like it might need a stack but actually reduces to two counters and a single pass. The key insight is that you only need to track how many characters are currently unmatched, not where they are.

Why this problem matters

This problem is the natural follow-up to Valid Parentheses. Instead of asking "is this string valid?" it asks "how far from valid is it?" The answer is exactly the number of unmatched characters, and counting them requires the same open/close balance logic you use for validation.

The greedy counter approach here also forms the foundation for harder problems like Minimum Remove to Make Valid Parentheses and Minimum Insertions to Balance a Parentheses String. Once you internalize the two-counter pattern, these variants become simple extensions.

The key insight: track two types of imbalance

Every invalid parentheses string has two kinds of unmatched characters:

1. Unmatched '(' characters that never found a closing ')' to their right.
2. Unmatched ')' characters that had no opening '(' to their left.

You need to add one ')' for each unmatched '(', and one '(' for each unmatched ')'. So the answer is simply the count of unmatched opens plus the count of unmatched closes.

The trick is that you can count both in a single left-to-right scan:

• When you see '(': increment open (it is tentatively unmatched).
• When you see ')': if open > 0, decrement open (you just matched a pending open). Otherwise, increment close (this close has no partner).

At the end, open holds the remaining unmatched opens and close holds the unmatched closes.

The greedy solution

def minAddToMakeValid(self, s: str) -> int:
    open_count = 0
    close_count = 0
    for c in s:
        if c == '(':
            open_count += 1
        else:
            if open_count > 0:
                open_count -= 1
            else:
                close_count += 1
    return open_count + close_count

Let's walk through each piece:

1. open_count tracks how many '(' characters are currently unmatched (waiting for a ')').
2. close_count tracks how many ')' characters had no '(' to pair with.
3. When you see '(', it might match a future ')', so increment open_count.
4. When you see ')', check if there is a pending open. If yes, decrement open_count (they matched). If no, this ')' is permanently unmatched, so increment close_count.
5. The answer is open_count + close_count, the total number of characters that need a partner added.

Visual walkthrough

Let's trace through s = "()))((" step by step. Watch how the counters change as we scan each character.

The final state is open=2, close=2. We need to add two ')' characters (for the unmatched opens) and two '(' characters (for the unmatched closes). Total additions: 4.

Complexity analysis

This is optimal. You need to look at every character at least once to know whether it is matched, so O(n) is the lower bound. And the two counters mean you never allocate any data structure that scales with input size.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Balance counting

The pattern of tracking a running balance to detect imbalance in paired sequences:

balance = 0
for item in sequence:
    if item == opener:
        balance += 1
    else:
        balance -= 1
    if balance < 0:
        handle_imbalance()

In this problem, the balance logic is split into two counters to separately track unmatched opens and closes. In Valid Parentheses, a single balance counter (or stack depth) suffices because you only need a boolean answer. In Longest Valid Parentheses, you use balance tracking from both directions. The core idea is the same: opens increment, closes decrement, and the sign of the balance tells you the state.

2. Greedy one-pass accumulation

The pattern of computing a result by accumulating information in a single scan without backtracking:

result = 0
state = initial_state
for item in sequence:
    update_state(item)
    if condition(state):
        result += contribution(state)
return result

In this problem, the "state" is the two counters and the "result" is their sum at the end. In Gas Station, the state is a running tank and the result is the candidate start. In Best Time to Buy and Sell Stock, the state is the running minimum and the result is the maximum difference. Greedy one-pass accumulation works whenever you can prove that going back to re-examine earlier elements would never improve the answer.

Edge cases

Before submitting, verify these:

• Already valid "()": open=0, close=0. Answer is 0. No additions needed.
• All opens "(((": open=3, close=0. Answer is 3. Need three closing parens.
• All closes ")))": open=0, close=3. Answer is 3. Need three opening parens.
• Empty string "": open=0, close=0. Answer is 0. Nothing to fix.
• Single character "(" or ")": Answer is 1 in both cases.
• Mixed unmatched "()))((": open=2, close=2. Answer is 4. Both types of imbalance present.
• Long alternating "()()()": All matched, answer is 0.

The counter solution handles all of these without any special-case logic.

Common mistakes

1. Using a single counter and taking its absolute value. If you just track balance (increment for '(', decrement for ')') and return abs(balance), you miss cases where both types of imbalance exist. For example, ")(" has balance 0 but needs 2 additions. You need separate tracking for unmatched opens and closes.

2. Resetting the counter when it goes negative. Some people reset a single balance counter to 0 when it goes negative and count the resets. This works for counting unmatched closes, but you also need to add the remaining balance at the end for unmatched opens. The two-counter approach avoids this confusion.

3. Using a stack when counters suffice. A stack works correctly but uses O(n) space. Since you only need the count (not the positions) of unmatched parens, two integers are enough.

From understanding to recall

You see the logic: scan left to right, two counters, one condition to decide between matching and counting. It is clean. But can you write it from scratch in 30 seconds without hesitating on which counter to increment when?

Under interview pressure, people mix up which counter to decrement, forget the open_count > 0 check, or accidentally return just one counter instead of their sum. These are recall failures, not understanding failures.

Spaced repetition closes that gap. You write the two-counter scan from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "minimum additions for valid parentheses" and the code flows out without hesitation.

The balance counting pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Valid Parentheses - The foundational stack-based parentheses matching problem
• Generate Parentheses - Generating all valid combinations using the same open/close balance logic
• Longest Valid Parentheses - Finding the longest valid substring using balance tracking

CodeBricks breaks the minimum add to make parentheses valid LeetCode problem into its balance counting and greedy accumulation building blocks, then drills them independently with spaced repetition. You type the two-counter loop from scratch until it is automatic. When a parentheses balance question shows up in your interview, you do not think about it. You just write it.