Domain 2MediumMEDIUM

Minimum Add to Make Parentheses Valid

Uses a greedy approach with two counters to track unmatched parentheses, achieving O(N) time and O(1) space complexity.

Domain: medium•Updated: 2026-09-04
#Greedy#Counter Simulation#O(N)#O(1)

Problem Breakdown

We are given a string S containing only '(' and ')'. The goal is to determine the minimum number of parentheses we need to insert—either at the beginning or end—to make the entire sequence valid according to standard parenthesis rules.

Inputs: A single string S consisting solely of characters '(' and ')'. Outputs: An integer representing the count of added parentheses required.

Implicit Constraints & Edge Cases:

  • The input length is small (<= 1000), so efficiency beyond linear time isn’t strictly necessary, but we should aim for optimal O(N)O(N).
  • Empty String: Should return 0.
  • All Open Parentheses (e.g., ”(((”): All need closing partners. The answer equals the length of the string.
  • All Closed Parentheses (e.g., ”))”): Each needs a preceding open partner. Answer equals length.
  • Already Valid: Returns 0.

Intuition

A naive brute-force approach would involve trying to insert parentheses at every possible position and checking validity for each combination, which leads to an exponential search space or high complexity due to repeated validation checks (O(N2)O(N^2) minimum).

The core insight is that we don’t need a literal stack data structure (like a Python list) if our goal is only the count of additions. We can simulate the behavior of a stack using two integer counters:

  1. left: Tracks unmatched open parentheses '('. When we encounter ')', if there are pending opens, they match and cancel out (decrement). If not (left == 0), this ')' is invalid on its own and requires a preceding '(' to be added.
  2. right_adds: Tracks the number of unmatched closing parentheses encountered when no open parenthesis was available.

After traversing the string, any remaining value in left represents unclosed opens that require corresponding closing brackets at the end. The total additions required is simply the sum of missing opening brackets (right_adds) and missing closing brackets (remaining left). This reduces space complexity from O(N)O(N) to O(1)O(1).

Approach

  1. Initialize two counters: left for unmatched open parentheses seen so far, and right_adds for the number of '(' needed before invalid ')'.
  2. Iterate through each character in string S:
    • If the character is '(', increment left. This represents a pending match waiting to be closed or needing a close later.
    • If the character is ')':
      • Check if we have an available open parenthesis (left > 0).
      • If yes, decrement left (we found a valid pair).
      • If no, increment right_adds. This signifies that this closing bracket has nothing to match with and requires us to add an opening bracket before it.
  3. After the loop finishes:
    • The variable right_adds holds the count of missing '(' for unmatched ')'.
    • The remaining value in left represents unclosed '(' that need closing brackets added after them.
  4. Return the sum of these two counts (right_adds + left).

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of string S. We traverse the input exactly once with constant-time operations per character.
  • Space Complexity: O(1)O(1). We only use a fixed number of integer variables regardless of input size (unlike using an explicit stack which would be O(N)O(N)).

Solution

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        # Counter for unmatched open parentheses encountered so far.
        left = 0
        
        # Counter for closing parentheses that need a preceding '(' to match them.
        right_adds = 0
        
        for char in s:
            if char == '(':
                # Found an opening bracket, increment pending count.
                left += 1
            else:
                # Encountered a closing bracket.
                if left > 0:
                    # Match it with the most recent unmatched open bracket.
                    left -= 1
                else:
                    # No available open bracket to match this close; 
                    # we must add an '(' before this ')'.
                    right_adds += 1
        
        # After traversal, 'left' contains unclosed opens needing ')' added at the end.
        # 'right_adds' contains closes that needed '(' added earlier.
        return left + right_adds

Edge Cases Handled

  • Empty String: The loop does not execute; left and right_adds remain 0, returning 0 correctly.
  • String with only '(': left increments for every char, right_adds stays 0. Returns total length (all need closing).
  • String with only ')': left remains 0; right_adds increments for every char. Returns total length (all need opening).
  • Already Valid String: Every '(' matches a subsequent ')'. Both counters end at 0, returning 0 correctly.