Leetcode 921. Minimum Add to Make Parentheses Valid

Let's understand what we're being asked to do. We have a string of parentheses like '(()' and need to count how many insertions are needed to make it valid.

Tracing through '(()': We have two opening '(' and only one closing ')'. The first '(' matches with ')', but the second '(' has no match. We need to insert one ')' at the end to balance it.

Another example: '())' has one opening '(' and two closing ')'. The first ')' matches with '(', but the second ')' has no opening bracket. We need to insert one '(' at the beginning.

Key insight: As we scan left-to-right, we can track unmatched opening brackets (need closing brackets later) and unmatched closing brackets (needed opening brackets earlier).

Edge cases to consider: What if the string is empty? (return 0). What if it's all opening brackets like '((('? (need 3 closing brackets). What if it's all closing brackets like ')))'? (need 3 opening brackets).

When scanning left-to-right, each '(' is a promise that we'll see a matching ')' later. Each ')' either fulfills a promise (matches a previous '(') or is unmatched (needs an insertion).

We can track the number of unfulfilled promises (unmatched opening brackets) as we go.

By maintaining a count of unmatched opening brackets, we can instantly determine if a closing bracket has a match or not.

If we see ')' and have unmatched '(' available, they cancel out. If we see ')' with no unmatched '(', we need to insert an opening bracket.

At the end, any leftover unmatched '(' need closing brackets inserted.

Think of it like a balance scale:

• Each '(' adds weight to the left side (unmatched openings)
• Each ')' removes weight from the left side (matches an opening)
• If the left side is empty when we see ')', we have an unmatched closing bracket
• At the end, any weight remaining on the left side represents unmatched opening brackets

Total insertions needed = unmatched closings + unmatched openings.

The optimal approach uses a greedy single-pass scan with a counter acting like a stack. Maintain a count of unmatched opening brackets. For each '(', increment the count. For each ')', if count is positive, decrement it (match found); otherwise, increment the unmatched closing count (no match available). After scanning, the total insertions needed is the sum of unmatched closing brackets and leftover unmatched opening brackets.

def min_add_to_make_valid(s):
    """
    Calculate minimum parentheses insertions needed to make string valid.
    Uses greedy single-pass scan with counter for unmatched opening brackets.
    """
    # Track unmatched opening and closing parentheses
    unmatched_open = 0
    unmatched_close = 0
    
    # Scan through each character
    for char in s:
        if char == '(':
            # Increment count of unmatched opening brackets
            unmatched_open += 1
        elif char == ')':
            # Check if we have an opening bracket to match
            if unmatched_open > 0:
                # Match found - decrement unmatched opening count
                unmatched_open -= 1
            else:
                # No match available - increment unmatched closing count
                unmatched_close += 1
    
    # Total insertions = unmatched closing + leftover opening
    result = unmatched_open + unmatched_close
    return result

• Greedy counting over stack: While parentheses problems often suggest using a stack, this problem can be solved more efficiently with two counters - one tracking unmatched opening parentheses and one tracking unmatched closing parentheses. This works because we only need the count of mismatches, not their positions.
• Left-to-right scanning strategy: Process the string in a single pass: increment a counter for each '(' and decrement for each ')'. When the counter would go negative, you've found an unmatched ')' that needs a matching '(' inserted - count it separately and reset to zero to continue scanning.
• Two-type mismatch handling: Recognize that parentheses invalidity comes from two distinct sources: (1) closing parentheses with no prior opening (handled during scan), and (2) leftover opening parentheses at the end (the final counter value). The answer is the sum of both types.
• Avoid premature stack usage: Don't reflexively reach for a stack just because you see parentheses - ask yourself if you need to track positions or just counts. If only counts matter and you're looking for minimum additions (not removals or reconstructions), simple counters suffice.
• O(1) space optimization insight: By using counters instead of a stack, we achieve O(1) space complexity versus O(n) for stack-based solutions. This matters for large inputs and demonstrates that understanding what information you actually need can dramatically improve space efficiency.
• Balance validation pattern: This greedy counting technique extends to any problem where you need to validate or fix sequential balance - think XML tag validation, chemical formula validation, or any domain where elements must be properly opened and closed in order.