The O(n) Club: Minimum Add to Make Parentheses Valid (And Why Your Editor Hates You)

The O(n) Club: Minimum Add to Make Parentheses Valid (And Why Your Editor Hates You)

⚡ TL;DR

Given a string made entirely of ‘(‘ and ‘)’, your job is to add as few parentheses as possible to make them all play nice and close up properly. You can sprinkle ‘(‘ or ‘)’ wherever your tired heart desires. Brute-force approach? Stack stack stack. But the real MVP is just counting as you scan. Here’s the speedy Java way:

// One-pass fix for your bracket headaches
int minAddToMakeValid(String s) {
    int open = 0, inserts = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') open++;
        else if (open > 0) open--;
        else inserts++;
    }
    return inserts + open;
}

🧠 How Devs Usually Mess This Up

Every dev’s first instinct: delete the weird extras, or treat all ‘)’ as the enemy. Nice try—wrong problem!

🔍 What’s Actually Going On

Picture this: it’s a parenthesis party. Each ‘(‘ walks in hoping their ‘)’ date arrives later. If a ‘)’ barges in single and nobody’s left to pair up? Time to call in backup and add an extra ‘(‘. At party’s end, any ‘(‘ still clutching punch need a ‘)’ summoned to close things out. So: scan through, keep a counter for openers, and every time you hit an unpaired ‘)’, queue a new ‘(‘. When the dust settles, your total insertions are: number of orphans you created plus the openers still needing closure.
(The only party where showing up uninvited makes the guest list longer!)

🛠️ PseudoCode

• Set open = 0 for the left parentheses waiting for their match.
• Set inserts = 0 for the parentheses you’ll shame-post insert.
• Walk through each character in the string:
  • If ‘(‘, increment open.
  • If ‘)’:
    • If open > 0, close one open parenthesis (–open).
    • If open == 0, increment inserts (need a new opener!).
• After the loop: add open to inserts, because all leftover ‘(‘ are unclosed.

💻 The Code

// O(n) time, O(1) space: no Stack, just guts
public int minAddToMakeValid(String s) {
    int open = 0, inserts = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') {
            open++;
        } else if (open > 0) {
            open--;
        } else {
            inserts++;
        }
    }
    return inserts + open;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Empty strings? Output’s 0—nothing to fix. (Don’t overthink it!)
• Strings stuffed with only ‘)’? All get matched with new ‘(‘. Output is length of string.
• Boring all-‘(‘ at the end? Each needs a ‘)’.
• Runtime: Single pass, O(n). Space: O(1). Not even a lonely Stack to leak memory.
• Don’t mix insert and remove: That’s a recipe for endless parentheses and existential pain.

🧠 Interviewer Brain-Tattoo

“If you’re asked to INSERT, don’t DELETE. This is algorithms, not your ex’s photos!”