Min Add to Make Parens Valid

Problem

Return the minimum number of "(" or ")" insertions to make the string a valid parenthesis sequence.

Constraints

• 1 ≤ s.length ≤ 1000

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def minAddToMakeValid(self, s):
        open_needed = 0
        bal = 0
        for c in s:
            if c == '(':
                bal += 1
            else:
                if bal == 0:
                    open_needed += 1
                else:
                    bal -= 1
        return open_needed + bal

Java

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.