LeetCode Entry

921. Minimum Add to Make Parentheses Valid

09.10.2024 medium 2024 kotlin rust

Minimum inserts to balance brackets

921. Minimum Add to Make Parentheses Valid medium blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/762

Problem TLDR

Minimum inserts to balance brackets #medium #stack

Intuition

The optimal way to return the balance is to insert lazily on every unbalanced position. (Prove is out of scope)

Now, to check the balance, let’s use a stack and match each open bracket with the closing. We can simplify the stack down to the counter.

Approach

  • keep the balance variable b separate from the insertions’ count variable res

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun minAddToMakeValid(s: String): Int {
        var b = 0; var res = 0
        for (c in s) if (c == '(') b++
            else if (b > 0) b-- else res++
        return res + b
    }



    pub fn min_add_to_make_valid(s: String) -> i32 {
        let (mut b, mut res) = (0, 0);
        for c in s.bytes() {
            if c == b'(' { b += 1 } else if b > 0 { b -= 1 }
            else { res += 1 }
        }; res + b
    }



    int minAddToMakeValid(string s) {
        int b = 0, res = 0;
        for (char c: s) if (c == '(') b++;
            else if (b > 0) b--; else res++;
        return res + b;
    }