Scale Engineer

Minimum Add to Make Parentheses Valid

Med
#0875Time: O(N), where N is the length of the string `s`. We iterate through the string exactly once.Space: O(1). We only use a few integer variables (`additions`, `balance`) to store our state, regardless of the input size.3 companies
Patterns
Greedy
Data structures
StringStack
Companies
NvidiaSiemensWalmart Labs

Prompt

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 ')'.

Approaches

2 approaches with complexity analysis and trade-offs.

A more optimized approach avoids using a stack and instead relies on a simple counter to keep track of the balance between open and close parentheses. This method achieves the same result with constant extra space.

Algorithm

  • Initialize two counters: additions = 0 and balance = 0.
  • Iterate through each character of the input string s.
  • If the character is (, it increases the number of unmatched open parentheses, so we increment balance.
  • If the character is ):
    • If balance > 0, it means there's an unmatched ( available to be paired. We decrement balance.
    • If balance == 0, this ) has no preceding (. It's an invalid parenthesis. We need to add one ( to fix it. So, we increment additions.
  • After iterating through the entire string, if balance is still positive, it represents the number of unmatched ( at the end of the string. Each of these requires a ) to be added.
  • The total minimum additions is the sum of additions (for invalid )) and the final balance (for unmatched ().

Walkthrough

Instead of using a stack, we can solve this problem by iterating through the string just once while keeping track of the 'balance' of the string. The balance counter represents the number of open parentheses that are waiting for a closing one.

  • We initialize balance and additions to zero.
  • When we encounter an opening parenthesis (, we increment balance because we now have one more open parenthesis that needs a match.
  • When we encounter a closing parenthesis ), we check the balance.
    • If balance is greater than 0, it means there's an open parenthesis waiting. We can use this ) to form a pair, so we decrement balance.
    • If balance is 0, it means there are no open parentheses waiting for a match. This ) is therefore invalid. To make it valid, we must insert an opening parenthesis. We count this by incrementing additions.

After the loop, the balance counter holds the number of opening parentheses that were never closed. To make the string valid, we need to add a closing parenthesis for each of these. So, the total number of additions is the additions we've counted so far, plus the final value of balance.

For example, with s = "()))((:

  • (: balance becomes 1.
  • ): balance becomes 0.
  • ): balance is 0, so additions becomes 1.
  • (: balance becomes 1.
  • (: balance becomes 2.
  • End of loop. Total additions = additions + balance = 1 + 2 = 3.
class Solution {    public int minAddToMakeValid(String s) {        int additions = 0;        int balance = 0;         for (char ch : s.toCharArray()) {            if (ch == '(') {                balance++;            } else if (ch == ')') {                if (balance > 0) {                    balance--;                } else {                    // This ')' has no matching '('.                    // We need to add a '(' to make it valid.                    additions++;                }            }        }         // After the loop, 'balance' is the number of unmatched '('.        // We need to add 'balance' number of ')' to make them valid.        additions += balance;         return additions;    }}

Complexity

Time

O(N), where N is the length of the string `s`. We iterate through the string exactly once.

Space

O(1). We only use a few integer variables (`additions`, `balance`) to store our state, regardless of the input size.

Trade-offs

Pros

  • Extremely efficient in terms of space, using only a constant amount of extra memory.

  • Very fast due to the simple single-pass logic with no overhead from complex data structures.

Cons

  • The logic might be slightly less intuitive at first glance compared to the direct simulation with a stack.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem