Minimum Add to Make Parentheses Valid

Minimum Add to Make Parentheses Valid

What is this problem about?

The Minimum Add to Make Parentheses Valid problem involves a string composed of ( and ) characters. A string is "valid" if every opening parenthesis has a matching closing parenthesis in the correct order. Your task is to determine the minimum number of parentheses (either opening or closing) you must add at any position to make the entire string valid.

Why is this asked in interviews?

This is a high-frequency Minimum Add to Make Parentheses Valid interview question because it is a foundational string-parsing problem. Companies like Microsoft and Meta use it to test if a candidate understands stack-based logic or "balance" counters. It's a great "warm-up" problem that can lead to more complex variations involving multiple types of brackets or dynamic programming.

Algorithmic pattern used

While you can use a Stack, the most memory-efficient Greedy interview pattern involves using two counters: balance and additions.

1. Iterate through the string.
2. If you see (, increment the balance.
3. If you see ), decrement the balance.
4. If balance becomes negative (meaning a ) appeared without a matching (), increment additions and reset balance to 0.
5. At the end, the total additions needed is additions + balance (the latter representing unclosed ().

Example explanation

Take the string ())((.

1. First char (: balance = 1.
2. Second char ): balance = 0.
3. Third char ): balance would be -1. Increment additions = 1, reset balance = 0.
4. Fourth char (: balance = 1.
5. Fifth char (: balance = 2. Final result: additions (1) + balance (2) = 3. We need to add one ( at the start and two ) at the end.

Common mistakes candidates make

• Only counting total '(' and ')': Thinking that if there are equal numbers of each, the string is valid. )( has equal counts but is invalid.
• Using a full Stack unnecessarily: While a stack works, it uses $O(N)$ space. A senior candidate should recognize that only the count of open parentheses matters, allowing for $O(1)$ space optimization.
• Forgetting unclosed opening parentheses: Only counting the "extra" closing parentheses and forgetting that ((( also requires three additions at the end.

Interview preparation tip

When dealing with parentheses, always think about "balance." Most of these problems can be solved by tracking how many "open" items are currently waiting for a "close" item. Mastering this Minimum Add to Make Parentheses Valid coding problem will help you solve harder problems like "Longest Valid Parentheses."