Minimum Add to Make Parentheses Valid

medium string stack greedy

Problem

Given a parentheses string, return the minimum number of '(' or ')' insertions needed to make it balanced.

Inputs = "())"

Output1

One '(' inserted at the front (or any valid position) fixes it.

def minAddToMakeValid(s):
    opens = 0  # unmatched '('
    adds = 0   # ')' we need to prepend
    for c in s:
        if c == '(':
            opens += 1
        else:
            if opens > 0: opens -= 1
            else: adds += 1
    return opens + adds

function minAddToMakeValid(s) {
  let opens = 0, adds = 0;
  for (const c of s) {
    if (c === '(') opens++;
    else {
      if (opens) opens--;
      else adds++;
    }
  }
  return opens + adds;
}

class Solution {
    public int minAddToMakeValid(String s) {
        int opens = 0, adds = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') opens++;
            else {
                if (opens > 0) opens--;
                else adds++;
            }
        }
        return opens + adds;
    }
}

int minAddToMakeValid(string s) {
    int opens = 0, adds = 0;
    for (char c : s) {
        if (c == '(') opens++;
        else {
            if (opens > 0) opens--;
            else adds++;
        }
    }
    return opens + adds;
}

Explanation

You do not need an actual stack here — two counters do the job. The idea is to track how many unmatched open parens are waiting (opens) and how many unmatched close parens you have already had to account for (adds).

Scan left to right. Every ( increases opens because it now needs a future ). Every ) tries to cancel one waiting open: if opens > 0 we decrement it, otherwise this close has nothing to pair with, so we increment adds — it will need a ( inserted before it.

At the end, opens is how many ) we still must add, and adds is how many ( we must add. The answer is simply opens + adds.

Example: s = "()))((". ( → opens=1; ) cancels → opens=0; the next two ) have no match → adds=2; then two ( → opens=2. Final answer is opens + adds = 2 + 2 = 4.

It works because a close paren with no waiting opener can never be fixed except by inserting an opener, and any openers still waiting at the end must each get a closer — so the two leftover counts add up to the minimum insertions.

Time: O(n) Space: O(1)