Leetcode 921. Minimum Add to Make Parentheses Valid
Given a string of '(' and ')', return the minimum number of parentheses insertions needed to make the string valid. This is solved greedily by scanning once and counting unmatched closing parentheses and leftover opening parentheses that require insertions.
Asked at:
Meta
DESCRIPTION
Given a string of '(' and ')', return the minimum number of parentheses insertions needed to make the string valid. This is solved greedily by scanning once and counting unmatched closing parentheses and leftover opening parentheses that require insertions.
Input:
s = "(()"
Output:
1
Explanation: We have two opening brackets and one closing bracket. The string needs one more closing bracket at the end to be valid: "(())"
Constraints:
- 1 <= s.length <= 10^5
- s consists only of '(' and ')' characters
Understanding the Problem
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).
Building Intuition
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.
Common Mistakes
Optimal Solution
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 parenthesesunmatched_open = 0unmatched_close = 0# Scan through each characterfor char in s:if char == '(':# Increment count of unmatched opening bracketsunmatched_open += 1elif char == ')':# Check if we have an opening bracket to matchif unmatched_open > 0:# Match found - decrement unmatched opening countunmatched_open -= 1else:# No match available - increment unmatched closing countunmatched_close += 1# Total insertions = unmatched closing + leftover openingresult = unmatched_open + unmatched_closereturn result
Start: Calculate minimum parentheses insertions needed
0 / 14
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) We scan through the string once, performing constant-time operations for each character
Space Complexity: O(1) We only use two integer counters regardless of input size
What We've Learned
- 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.
Related Concepts and Problems to Practice
easy
This is the foundational parentheses validation problem that directly relates to the given problem. While the original problem counts insertions needed, this problem validates matching parentheses using the same core stack-based pattern for tracking opening and closing brackets.
hard
This problem extends parentheses validation concepts by finding the longest valid substring. It uses similar stack-based tracking of unmatched parentheses and requires understanding when parentheses are balanced versus when insertions would be needed, making it an excellent progression from the minimum insertions problem.
medium
While using a different technique (backtracking), this problem reinforces understanding of valid parentheses structure by generating all valid combinations. It requires tracking the balance between opening and closing parentheses, which is the same core concept needed to determine minimum insertions.
Test Your Understanding
Why is stack the right data structure for this problem?
stack provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early December, 2025
Meta
Manager
Late November, 2025
Meta
Staff
Late November, 2025
Meta
Senior
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.