AlgoMaster Logo

Minimum Add to Make Parentheses Valid

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We have a string consisting only of ( and ) characters, and we need the minimum number of insertions that makes every parenthesis properly matched. We only insert characters, never remove them, so each parenthesis already in the string stays. The answer is the count of parentheses that are currently unmatched, because each one requires exactly one insertion to fix.

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

There are two ways a parenthesis goes unmatched. Scanning left to right, a ) is unmatched when no open ( is waiting for it. A ( is unmatched when it reaches the end of the string without a ) pairing with it. Counting both types and summing them gives the answer.

Key Constraints:

  • 1 <= s.length <= 1000: The string is short, so the linear solution below runs in well under a millisecond. The same approach scales to far longer inputs without change.
  • s[i] is either '(' or ')'. There are no letters or other characters, so every character is one of the two parentheses.

Approach 1: Stack-Based Matching

Intuition

A stack tracks which opening parentheses are still waiting for a match. Push every (. On each ), try to match it with a ( from the top of the stack. If the stack is not empty, pop it (a matched pair). If the stack is empty, this ) has no ( before it to pair with, so it is unmatched and needs a ( inserted 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 uses O(n) extra space, yet the only thing it reads from the stack is its size, never the elements. The next approach replaces the stack with a single counter and drops the space to O(1).

Approach 2: Two Counters (Optimal)

Intuition

Since the string only contains ( and ), a full stack is unnecessary. Every element pushed in Approach 1 is the same character (, so the stack carries no information beyond its height. A counter unmatchedOpen holds that height directly: the number of unmatched ( seen so far.

On (, increment unmatchedOpen. On ), decrement unmatchedOpen if it is positive (an unmatched ( is available to pair with), otherwise increment a separate counter unmatchedClose (no ( is available, so this ) is unmatched). The answer is unmatchedOpen + unmatchedClose.

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