AlgoMaster Logo

Minimum Add to Make Parentheses Valid

Last Updated: April 2, 2026

medium
3 min read

Understanding the Problem

We have a string consisting only of ( and ) characters, and we need to figure out the minimum number of insertions to make every parenthesis properly matched. Notice that we're inserting characters, not removing them. But the question boils down to the same core insight: how many parentheses are currently unmatched?

Every unmatched ( needs a ) inserted somewhere after it. Every unmatched ) needs a ( inserted somewhere before it. So the answer is simply the total count of unmatched parentheses.

The key observation is this: as you scan left to right, an unmatched ) is one that appears when there are no open ( characters waiting for a match. And an unmatched ( is one that never finds a corresponding ) by the time you reach the end of the string. If we can count both types, their sum is our answer.

Key Constraints:

  • 1 <= s.length <= 1000 — Even O(n^2) would work fine here, but we should still aim for O(n) since the problem has a clean linear solution.
  • s[i] is either '(' or ')' — No letters or other characters to worry about. Every character is a parenthesis.

Approach 1: Stack-Based Matching

Intuition

The most natural way to think about parentheses matching is with a stack. When you see an (, push it. When you see a ), try to match it with a ( from the stack. If you can, pop the stack (matched pair). If you can't (stack is empty), this ) is unmatched and we'll need to insert a ( for it.

After scanning the entire string, any ( characters still on the stack are unmatched and each needs a ) inserted. So the answer is: unmatched ) we found during the scan + unmatched ( left on the stack.

Algorithm

  1. Initialize an empty stack and a counter unmatchedClose set to 0.
  2. Iterate through each character in the string:
    • If the character is (, push it onto the stack.
    • If the character is ):
      • If the stack is not empty, pop the top (matched pair found).
      • If the stack is empty, increment unmatchedClose (this ) has no match).
  3. After the loop, the stack size gives us the number of unmatched (.
  4. Return stack.size() + unmatchedClose.

Example Walkthrough

1Initialize: scan left to right, stack=[], unmatchedClose=0
0
(
i
1
)
2
)
3
(
4
(
1/6

Code

The stack approach works but uses O(n) extra space. Notice we never look at what's on the stack, only its size. What if we replaced the stack with a simple counter?

Approach 2: Two Counters (Optimal)

Intuition

Since the string only contains ( and ), we don't need a full stack. Every element on the stack is the same character (, so the stack is really just a number: how many unmatched ( we've seen so far. We can replace it with a counter called unmatchedOpen.

When we see (, increment it. When we see ), either decrement unmatchedOpen (if positive, meaning there's an unmatched ( to pair with) or increment a separate counter unmatchedClose (if unmatchedOpen is zero, meaning this ) has no match). At the end, unmatchedOpen + unmatchedClose is our answer.

Algorithm

  1. Initialize two counters: unmatchedOpen = 0 and unmatchedClose = 0.
  2. Iterate through each character in the string:
    • If the character is (, increment unmatchedOpen.
    • If the character is ):
      • If unmatchedOpen > 0, decrement unmatchedOpen (matched a pair).
      • Otherwise, increment unmatchedClose (no ( available to match).
  3. Return unmatchedOpen + unmatchedClose.

Example Walkthrough

1Initialize: unmatchedOpen=0, unmatchedClose=0
0
(
i
1
)
2
)
3
)
4
(
5
(
1/7

Code