DSA sheet · Stack · Pattern 4: parentheses & scoring

Minimum Add to Make Parentheses Valid

The second question of the parentheses pattern. The teacher's message: if you really understood Valid Parentheses, you can almost solve this alone. Instead of answering "valid or not", we now count how many brackets are broken. She first explains why trying every insertion is hopeless (exponential), then reuses the Valid Parentheses stack with one counter, and finally removes the stack and keeps just two integers. That last step (O(1) space) is the one she says impresses interviewers.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks from scratch + the parentheses pattern
• Part A · Brute force: try every insertion (why it fails)
• Part B · Stack + a counter for extra closers
• Part C · Space optimised: two counters, no stack
• Part D · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile of plates: you add on top and take from the top. The last thing in is the first thing out, called LIFO (Last In, First Out).

Drawings: stack written left = bottom, right = top. In vertical pictures the top is red.

The parentheses pattern (recap from Valid Parentheses)

• Opener ( → push; it waits for its partner.
• Closer ) → if an opener is waiting, pop it (a matched pair cancels out).
• Whatever can't be matched is "broken".

The counter trick

Here the string has only round brackets. All waiting openers are identical ( characters, so the stack holds nothing useful except how many there are. An integer open can replace it: push ⇒ open += 1, pop ⇒ open -= 1, "stack not empty" ⇒ open > 0. Space goes from O(n) to O(1). This only works when there is one bracket family; with ( [ { mixed we must remember the kinds, so the stack is needed.

Part A · Brute force: try every insertion

LeetCode 921

1The question in simple words

You get a string s of ( and ). In one move you may insert one bracket (either kind) anywhere. Return the smallest number of insertions that makes the string valid (balanced).

Important: the question asks only how many, not where. For ()) you could write (()) or ()(); for the second string ()(()) or ()()(). Different positions, same count. So don't waste effort deciding positions.

2What the constraints tell us

• 1 ≤ s.length ≤ 1000 (10³), and only ( / ) → one bracket family (so the counter trick will be possible).
• Speed check: O(n²) = 10⁶ is fine. O(n³) = 10⁹ is TLE, since roughly 10⁸ simple operations fit in one second (a bit more sometimes, but never 10⁹).
• So anything exponential is completely out of the question.

3Intuition of the brute force

"Try adding brackets and test with Valid Parentheses" is the first idea. That's why the teacher said Valid Parentheses is a prerequisite: the brute force calls it as a helper.

But we don't know which kind to add, where to add it, or how many are needed. So we have to try: every single insertion (every position × both kinds) and test each; if none is valid, every pair of insertions; then every triple…

4Why it blows up

Take ((. Suppose we already guessed "we need closers". Put one ) at the front, test → no. In the middle → no. At the end → no. Now try two: ))(( no, )(() no, … until one works. Each extra bracket multiplies the number of strings by about (length + 1) × 2.

The worst case is 1000 openers: we'd need 1000 insertions, and the number of strings to test explodes. Exponential: it won't run even for n = 30. The teacher doesn't code it for that reason. We show a tiny version below only to see the idea (and to check the fast answers on short strings).

5Approach steps

1. Start with the set {s} and k = 0.
2. If any string in the set is valid → return k.
3. Otherwise make a new set: every string with one more bracket inserted at every position.
4. k += 1 and repeat.

6Code (Python)

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        def is_valid(t):                       # Valid Parentheses, one family
            stack = []
            for ch in t:
                if ch == '(':
                    stack.append(ch)
                elif not stack:
                    return False
                else:
                    stack.pop()
            return not stack

        current = {s}
        k = 0
        while True:
            if any(is_valid(t) for t in current):
                return k
            bigger = set()
            for t in current:                  # insert one more bracket everywhere
                for pos in range(len(t) + 1):
                    for b in "()":
                        bigger.add(t[:pos] + b + t[pos:])
            current = bigger
            k += 1

7Code line by line

8Dry run: ())

1. k = 0: is ()) valid? No.
2. Build all 1-insertion strings: (()), )()), (()))… (8 positions × kinds, some repeat).
3. k = 1: (()) is valid → return 1 ✓

9Complexity & remember

• Time exponential (about (2(n+1))^k strings, each checked in O(n)). Space also exponential for the sets. Not submittable.

Part B · Stack + a counter for extra closers

1The question (same)

Minimum insertions to balance a string of ( and ).

2Constraints

n ≤ 1000. One pass, O(n), is trivially fast.

3Intuition: cancel what you can, count what's left

Run the Valid Parentheses stack. Every matched pair cancels itself, so it needs nothing. Only unmatched brackets need help, and there are exactly two kinds of unmatched brackets:

• A ) that arrives when no opener is waiting. It needs one ( added before it. Count these in a variable closing.
• A ( that is still on the stack at the end. Nobody closed it, so it needs one ) added after it. Their count is len(stack).

Each unmatched bracket needs exactly one partner, so answer = len(stack) + closing.

4Building the logic from examples

Example 1: ())

( push. ) pops it (pair done). ) arrives, stack empty → there's no opener for it → closing += 1. End: stack empty, closing = 1 → answer 1.

Notice: in Valid Parentheses an empty stack on a closer meant "return False". Here it means "count one problem and keep going".

Example 2: )((()

The first ) has nothing before it → closing = 1. Then three ( are pushed. The final ) pops one of them. At the end the stack still holds two (.

Minimum add = minimum delete

The teacher points out a twin problem: "minimum deletions to make it valid". The answer is the same number. Each unmatched bracket can be fixed either by adding its partner or by deleting it, and either way it costs exactly one move per unmatched bracket.

5Approach steps

1. stack = [], closing = 0.
2. For each ch: if ( → push.
3. If ): if the stack is not empty → pop (a pair); else → closing += 1.
4. Return len(stack) + closing.

6Code (Python)

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []
        closing = 0                  # ')' that had no '(' before them
        for ch in s:
            if ch == '(':
                stack.append(ch)
            else:                    # ch == ')'
                if stack:
                    stack.pop()      # matched pair, cancels out
                else:
                    closing += 1     # needs one '(' inserted
        return len(stack) + closing  # leftover '(' each need a ')'

7Code line by line

8Dry run: )((()

9Complexity & remember

• Time O(n): one pass, O(1) per character.
• Space O(n): the stack can hold every character (e.g. (((().

Part C · Space optimised: two counters, no stack

1The question (same)

Same problem. Same O(n) time. We only want to cut the space.

2Constraints

Only ( and ): one family. That's exactly the condition for the counter trick.

3Intuition

Look at what Part B pushes: always the same character (. What do we ever ask the stack? Only "is it empty?" and, at the end, "how big is it?". Both are answered by a number. So replace the stack with an integer open = number of openers currently waiting.

4The mapping, line by line

The teacher stresses that nothing else changes: same logic, same answers, just a number instead of a list.

5Approach steps

1. open = 0, closing = 0.
2. ( → open += 1.
3. ) → if open > 0: open -= 1; else closing += 1.
4. Return open + closing.

6Code (Python)

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        open_count = 0               # '(' still waiting for a ')'
        closing = 0                  # ')' that found no '('
        for ch in s:
            if ch == '(':
                open_count += 1
            elif open_count > 0:
                open_count -= 1      # this ')' closes a waiting '('
            else:
                closing += 1         # this ')' needs an extra '('
        return open_count + closing

We name it open_count because open is a built-in function in Python (shadowing it works, but is a bad habit).

7Code line by line

8Dry run: ())((

One fix: ()()(()) → 3 insertions ✓. Note the order matters: the ) at index 2 can't be matched by the (s that come after it, That's why simply comparing totals fails: the string has 3 openers and 2 closers, so |3 − 2| = 1, but the true answer is 3. Order matters, and the counters track order as they walk.

9Complexity & remember

• Time O(n), the same as the stack. Space O(1): just two integers.
• Teacher's tip: explain the stack version first, then say "since there's only one bracket type, I can replace the stack with a counter". Showing that step impresses the interviewer.

Part D · Revision page

s = Solution()
print(s.minAddToMakeValid("())"))     # 1
print(s.minAddToMakeValid("((("))     # 3
print(s.minAddToMakeValid("()(("))    # 2
print(s.minAddToMakeValid(")((()"))   # 3
print(s.minAddToMakeValid(")("))      # 2
print(s.minAddToMakeValid("()()"))    # 0

Based on this video: Minimum Add to Make Parentheses Valid | Stack pattern: parentheses & scoring