Minimum Add to Make Parentheses Valid Coding Problem

“Minimum Add to Make Parentheses Valid” is one of those deceptively simple string problems that shows up a lot in coding interviews because it tests whether you truly understand balanced parentheses, not whether you can write fancy code.

You’re given a string made up of just ( and ). Your goal is to figure out the minimum number of parentheses you must add (anywhere in the string) to make the entire string valid.

A valid parentheses string follows two rules:

• Every opening parenthesis ( must be matched with a closing parenthesis ).
• At no point while scanning left to right should you have more ) than (. (Because a closing parenthesis can’t match something that hasn’t appeared yet.)

So strings like () and (())() are valid. Strings like (() or ())( are not. What makes this problem useful for interview prep is that you’re not asked to “fix” the string explicitly; you’re asked to count the minimum insertions needed to make it valid.

Want to explore more coding problem solutions? Check out the Longest String Chain and Largest Divisible Subset coding problem solutions.

The core idea behind the solution

The clean solution comes from scanning the string once and tracking two things:

• How many opening parentheses are currently unmatched (think of it as a “balance” of opens).
• How many closing parentheses are missing because you encountered a ) that had nothing to match.

Step-by-step reasoning (no code)

1. Start with:

open_needed = 0 (unmatched ( so far)

additions = 0 (how many parentheses we need to add)

1. Walk through the string from left to right:

If you see (:

It creates a new, unmatched opening, so increase open_needed.

If you see ):

If open_needed is greater than 0, this ) can match a previous (, so decrease open_needed.

If open_needed is 0, this ) is “extra”, it has nothing to match, so the only way to fix it is to add an opening parenthesis before it. That means increase additions.

1. After scanning the entire string:

If open_needed is still greater than 0, those are unmatched (.

The only way to fix them is to add that many ) at the end (or somewhere later).

So the final answer is:

additions + open_needed

Why this works (the interview explanation)

This approach works because it mirrors the exact definition of a valid parentheses string:

Any time you see an unmatched ), the only fix is to insert a ( somewhere before it.

Any ( that remains unmatched at the end must be closed by adding ).

It’s also optimal because you never add parentheses unless you are forced to:

• You only add ( when a ) cannot be matched.
• You only add ) for leftover unmatched (.

Complexity and why interviewers like it

This solution is efficient and clean:

• Time complexity: O(n) because you scan once.
• Space complexity: O(1) because you only use counters.

Interviewers like this problem because it tests if you can:

• Maintain a running invariant (balance of opens)
• Handle edge cases like strings starting with ) or ending with lots of (
• Explain correctness clearly without relying on trial-and-error