Minimum Add to Make Parentheses Valid Solution

The problem

A parentheses string is valid if and only if:

It is the empty string,
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

Example 1:

Input: s = "())"
Output: 1

Example 2:

Input: s = "((("
Output: 3

Constraints:

1 <= s.length <= 1000
s[i] is either '(' or ')'.

Approach overview

Problem Overview: You get a string containing only '(' and ')'. The goal is to compute the minimum number of parentheses you must add so the final string becomes a valid parentheses sequence. A valid sequence means every opening parenthesis has a matching closing parenthesis and pairs appear in the correct order.

Approach 1: Greedy Balance Tracking (O(n) time, O(1) space)

This approach scans the string once while tracking a running balance of open parentheses. When you see '(', increment the balance because it expects a future closing bracket. When you see ')', decrement the balance. If the balance becomes negative, it means a closing parenthesis appeared without a matching opening one, so you must add an opening parenthesis and reset the balance to zero. After finishing the scan, any remaining positive balance represents unmatched opening parentheses, which require additional closing parentheses.

The key insight: every invalid ')' requires an inserted '(', and every leftover '(' requires a ')'. This greedy rule works because parentheses validity only depends on the running balance, not on rearranging characters. Time complexity is O(n) because you iterate once through the string, and space complexity is O(1) since only counters are stored. This method fits well with problems tagged under Greedy and String.

Approach 2: Stack Simulation (O(n) time, O(n) space)

This method explicitly simulates parentheses matching using a stack. Traverse the string character by character. Push every '(' onto the stack. When encountering ')', check the top of the stack: if an opening parenthesis exists, pop it to form a valid pair. If the stack is empty, the closing parenthesis has no match, so increment the required additions counter.

After processing the entire string, the stack may still contain unmatched opening parentheses. Each remaining element requires one closing parenthesis to make the string valid. The total additions equal the unmatched closing count plus the remaining stack size. This approach has O(n) time complexity because each character is processed once and stack operations are constant time. Space complexity is O(n) due to the stack storing unmatched parentheses. It mirrors the classic pattern used in many Stack problems.

Recommended for interviews: Greedy balance tracking is the expected solution. It achieves the same correctness as the stack simulation but reduces space from O(n) to O(1). Interviewers like to see the stack approach first because it demonstrates understanding of parentheses matching, then the greedy optimization that removes the extra memory.

Approach 1: Greedy Balance Tracking

This approach involves iterating through the string and using a balance counter to track the validity of the sequence.

We increment the balance for every opening parenthesis '(' and decrement it for a closing parenthesis ')'. If, at any point, the balance becomes negative, it means we have an extra closing parenthesis, and we need to increase the count of steps required to balance the string. By the end of the iteration, the balance will also tell us how many opening parentheses need to be closed to make the string valid.

Python

def min_add_to_make_valid(s: str) -> int:
    balance = 0
    result = 0
    for char in s:
        balance += 1 if char == '(' else -1
        if balance == -1:
            result += 1
            balance += 1
    return result + balance

s = ')((('
print(min_add_to_make_valid(s))

Java

public class Main {
    public static int minAddToMakeValid(String s) {
        int balance = 0, result = 0;
        for (char c : s.toCharArray()) {
            balance += (c == '(') ? 1 : -1;
            if (balance == -1) {
                result++;
                balance++;
            }
        }
        return result + balance;
    }

    public static void main(String[] args) {
        String s = ")((";
        System.out.println(minAddToMakeValid(s));
    }
}

C++

#include <iostream>
#include <string>

int minAddToMakeValid(std::string s) {
    int balance = 0, result = 0;
    for (char ch : s) {
        balance += (ch == '(') ? 1 : -1;
        if (balance == -1) {
            result++;
            balance++;
        }
    }
    return result + balance;
}

int main() {
    std::string s = ")((";
    std::cout << minAddToMakeValid(s) << std::endl;
    return 0;
}

JavaScript

function minAddToMakeValid(s) {
    let balance = 0;
    let result = 0;
    for (let char of s) {
        balance += (char === '(') ? 1 : -1;
        if (balance === -1) {
            result++;
            balance++;
        }
    }
    return result + balance;
}

const s = ")((";
console.log(minAddToMakeValid(s));

#include <stdio.h>
#include <string.h>

int minAddToMakeValid(char * s) {
    int balance = 0, result = 0;
    for (int i = 0; i < strlen(s); i++) {
        balance += (s[i] == '(') ? 1 : -1;
        if (balance == -1) {
            result++;
            balance++;
        }
    }
    return result + balance;
}

int main() {
    char s[] = ")((";
    printf("%d\n", minAddToMakeValid(s));
    return 0;
}

using System;

class Program {
    public static int MinAddToMakeValid(string s) {
        int balance = 0, result = 0;
        foreach (char c in s) {
            balance += (c == '(') ? 1 : -1;
            if (balance == -1) {
                result++;
                balance++;
            }
        }
        return result + balance;
    }

    static void Main() {
        string s = ")((";
        Console.WriteLine(MinAddToMakeValid(s));
    }
}

The Python solution iterates through each character and updates the balance and result as needed, similar to other languages.

Complexity

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

Try this approach in the editor

Approach 2: Stack Simulation

In this approach, we leverage a stack structure to simulate parentheses placement, assisting in counting the balance.

Iterate over the string, pushing opening parentheses onto the stack and popping for each encountered closing parenthesis when possible. When a closing parenthesis finds no partner to pop, increase the invalid count, simulating the need for one more opening parenthesis. In the end, the stack length represents unmatched opening parentheses.

Python

def min_add_to_make_valid(s: str) -> int:
    stack = 0
    invalid = 0
    for char in s:
        if char == '(': 
            stack += 1
        elif stack > 0:
            stack -= 1
        else:
            invalid += 1
    return invalid + stack

s = ')(()'
print(min_add_to_make_valid(s))

Java

public class Main {
    public static int minAddToMakeValid(String s) {
        int stack = 0, invalid = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack++;
            } else if (stack > 0) {
                stack--;
            } else {
                invalid++;
            }
        }
        return invalid + stack;
    }

    public static void main(String[] args) {
        String s = ")(()";
        System.out.println(minAddToMakeValid(s));
    }
}

C++

#include <iostream>
#include <string>

int minAddToMakeValid(std::string s) {
    int stack = 0, invalid = 0;
    for (char ch : s) {
        if (ch == '(') {
            stack++;
        } else {
            if (stack > 0) {
                stack--;
            } else {
                invalid++;
            }
        }
    }
    return invalid + stack;
}

int main() {
    std::string s = ")(()";
    std::cout << minAddToMakeValid(s) << std::endl;
    return 0;
}

JavaScript

function minAddToMakeValid(s) {
    let stack = 0;
    let invalid = 0;
    for (let char of s) {
        if (char === '(') {
            stack++;
        } else if (stack > 0) {
            stack--;
        } else {
            invalid++;
        }
    }
    return invalid + stack;
}

const s = ")(()";
console.log(minAddToMakeValid(s));

#include <stdio.h>
#include <string.h>

int minAddToMakeValid(char * s) {
    int stack = 0, invalid = 0;
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == '(') {
            stack++;
        } else {
            if (stack > 0) {
                stack--;
            } else {
                invalid++;
            }
        }
    }
    return invalid + stack;
}

int main() {
    char s[] = ")(()";
    printf("%d\n", minAddToMakeValid(s));
    return 0;
}

using System;

class Program {
    public static int MinAddToMakeValid(string s) {
        int stack = 0, invalid = 0;
        foreach (char c in s) {
            if (c == '(') {
                stack++;
            } else if (stack > 0) {
                stack--;
            } else {
                invalid++;
            }
        }
        return invalid + stack;
    }

    static void Main() {
        string s = ")(()";
        Console.WriteLine(MinAddToMakeValid(s));
    }
}

The Python version uses simple integer counters to track stack size and invalid closes.

Complexity

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

Try this approach in the editor

Approach 3: Greedy + Stack

This problem is a classic parenthesis matching problem, which can be solved using "Greedy + Stack".

Iterate through each character c in the string s:

If c is a left parenthesis, directly push c into the stack;
If c is a right parenthesis, at this point if the stack is not empty, and the top element of the stack is a left parenthesis, then pop the top element of the stack, indicating a successful match; otherwise, push c into the stack.

After the iteration ends, the number of remaining elements in the stack is the number of parentheses that need to be added.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.

TypeScript

function minAddToMakeValid(s: string): number {
    const stk: string[] = [];
    for (const c of s) {
        if (c === ')' && stk.length > 0 && stk.at(-1)! === '(') {
            stk.pop();
        } else {
            stk.push(c);
        }
    }
    return stk.length;
}

func minAddToMakeValid(s string) int {
	stk := []rune{}
	for _, c := range s {
		if c == ')' && len(stk) > 0 && stk[len(stk)-1] == '(' {
			stk = stk[:len(stk)-1]
		} else {
			stk = append(stk, c)
		}
	}
	return len(stk)
}

Try this approach in the editor

Approach 4: Greedy + Counting

Solution 1 uses a stack to implement parenthesis matching, but we can also directly implement it through counting.

Define a variable cnt to represent the current number of left parentheses to be matched, and a variable ans to record the answer. Initially, both variables are set to 0.

Iterate through each character c in the string s:

If c is a left parenthesis, increase the value of cnt by 1;
If c is a right parenthesis, at this point if cnt > 0, it means that there are left parentheses that can be matched, so decrease the value of cnt by 1; otherwise, it means that the current right parenthesis cannot be matched, so increase the value of ans by 1.

After the iteration ends, add the value of cnt to ans, which is the answer.

The time complexity is O(n), and the space complexity is O(1), where n is the length of the string s.

TypeScript

function minAddToMakeValid(s: string): number {
    let [ans, cnt] = [0, 0];
    for (const c of s) {
        if (c === '(') {
            ++cnt;
        } else if (cnt) {
            --cnt;
        } else {
            ++ans;
        }
    }
    ans += cnt;
    return ans;
}

func minAddToMakeValid(s string) int {
	ans, cnt := 0, 0
	for _, c := range s {
		if c == '(' {
			cnt++
		} else if cnt > 0 {
			cnt--
		} else {
			ans++
		}
	}
	ans += cnt
	return ans
}

Try this approach in the editor

Approach 5: Replace + recursion

TypeScript

function minAddToMakeValid(s: string): number {
    const l = s.length;
    s = s.replace('()', '');

    return s.length === l ? l : minAddToMakeValid(s);
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Balance Tracking	Time Complexity: O(n). Space Complexity: O(1).
Stack Simulation	Time Complexity: O(n). Space Complexity: O(1).
Greedy + Stack	–
Greedy + Counting	–
Replace + recursion	–

Complexity analysis

Approach	Time	Space	When to Use
Greedy Balance Tracking	O(n)	O(1)	Best general solution when only the count of additions is required and memory efficiency matters
Stack Simulation	O(n)	O(n)	Useful for learning parentheses matching or when you need explicit tracking of unmatched characters

Frequently asked questions

Is Minimum Add to Make Parentheses Valid easy or hard?

This problem is generally rated Medium because it requires recognizing that stack simulation can be optimized to a greedy counter approach. The logic is simple once you understand parentheses balance, but identifying the O(1) space optimization is the key insight.

How to solve Minimum Add to Make Parentheses Valid in O(n)?

Scan the string and maintain a balance counter for open parentheses. Increment for '(' and decrement for ')'. If the counter becomes negative, add one required opening parenthesis and reset the balance. After the scan, add the remaining balance to the result because each unmatched '(' needs a closing ')'.

Minimum Add to Make Parentheses Valid Python or Java solution?

Both Python and Java implementations typically use the greedy balance method. Iterate through the string, track the number of open parentheses, and count how many insertions are required when unmatched closing brackets appear. The algorithm runs in O(n) time and constant space.

What is the best approach for Minimum Add to Make Parentheses Valid?

Greedy balance tracking is the best approach. Iterate through the string while maintaining a counter for unmatched opening parentheses. When a closing parenthesis appears without a matching open one, increment the required additions. This solution runs in O(n) time and O(1) space, which is optimal.

What data structure is used in Minimum Add to Make Parentheses Valid?

Two common approaches exist. A stack can simulate parentheses matching by pushing '(' and popping when encountering ')'. A more optimal solution replaces the stack with a simple integer balance counter using a greedy strategy.

What is the time complexity of Minimum Add to Make Parentheses Valid?

The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once while updating a balance counter or stack. The greedy method uses O(1) space, while the stack-based method uses O(n) space in the worst case.

Is Minimum Add to Make Parentheses Valid asked at Google, Amazon, or Meta?

Parentheses validation and balancing problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants include Valid Parentheses, Minimum Remove to Make Valid Parentheses, and longest valid parentheses, all testing stack or greedy reasoning.

Minimum Add to Make Parentheses Valid solution and explanation

The problem

Approach overview

Approach 1: Greedy Balance Tracking

Approach 2: Stack Simulation

Approach 3: Greedy + Stack

Approach 4: Greedy + Counting

Approach 5: Replace + recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Add to Make Parentheses Valid solution and explanation

The problem

Approach overview

Approach 1: Greedy Balance Tracking

Approach 2: Stack Simulation

Approach 3: Greedy + Stack

Approach 4: Greedy + Counting

Approach 5: Replace + recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems