Minimum Insertions to Balance a Parentheses String - Solution & Explanation
Problem Statement
Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:
- Any left parenthesis
'('must have a corresponding two consecutive right parenthesis'))'. - Left parenthesis
'('must go before the corresponding two consecutive right parenthesis'))'.
In other words, we treat '(' as an opening parenthesis and '))' as a closing parenthesis.
- For example,
"())","())(())))"and"(())())))"are balanced,")()","()))"and"(()))"are not balanced.
You can insert the characters '(' and ')' at any position of the string to balance it if needed.
Return the minimum number of insertions needed to make s balanced.
Example 1:
Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to add one more ')' at the end of the string to be "(())))" which is balanced.
Example 2:
Input: s = "())" Output: 0 Explanation: The string is already balanced.
Example 3:
Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.
Constraints:
1 <= s.length <= 105sconsists of'('and')'only.
Approach Overview
Problem Overview: You are given a parentheses string where every '(' must be matched with exactly two consecutive ')'. The task is to compute the minimum number of insertions required to make the string valid under this rule.
Approach 1: Stack-based Analysis (O(n) time, O(n) space)
This approach simulates the validation process using a stack. Iterate through the string and push '(' onto the stack. When encountering ')', check whether it forms a pair with the next character to represent the required '))'. If a pair is incomplete, count the insertion needed. The stack tracks unmatched opening brackets and ensures each one receives exactly two closing brackets. This mirrors classical stack-based parenthesis validation but adapts the rule to handle double closing brackets.
Approach 2: Single Pass Counting (Greedy) (O(n) time, O(1) space)
The optimal solution avoids a stack and processes the string using counters. Maintain two variables: one for the number of required closing parentheses (need) and one for insertions performed. Every '(' increases the required closing count by two. If the current requirement becomes odd, insert one ')' to maintain the '))' pairing rule. When encountering ')', decrease the requirement. If the requirement becomes negative, insert an opening bracket before it and reset the needed closing count. This greedy strategy ensures the string stays balanced as you scan left to right using constant memory. The approach relies on careful counting rather than explicit structure tracking and is common in greedy and string parsing problems.
Recommended for interviews: The single-pass greedy counting solution is the expected answer. It runs in O(n) time with O(1) space and demonstrates strong reasoning about invariants while scanning a string. The stack version helps explain the mechanics of matching parentheses, but interviewers usually look for the constant-space greedy insight.
Approach 1: Single Pass Counting
In this approach, we'll keep track of the unmatched left parentheses '(' and needed right parentheses ')'. As we traverse the string, we'll adjust our counters based on the current character.
- If the character is '(', increment the left count.
- If the character is ')', decrement the right count. However, if right is zero, it means there's an unmatched ')'.
At the end, the sum of remaining left needs to be paired with ''))'' and any unmatched right will give us the total number of insertions required.
This solution efficiently counts the number of insertions required by simulating the operation of the string as per balanced requirements. The main work is done in a single pass through the string.
Complexity
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), using constant space for variables.
Approach 2: Stack-based Analysis
We can solve this using a stack to better visualize the process of seeing parenthesis as matched pairs. By pushing and popping elements, we simulate the pairing of '(' with '))'.
Use a stack data structure to manage leftover unmatched '(' parenthesis while iterating over the string to determine the complement needed for each unmatched pair.
This solution efficiently uses a stack to count how many unmatched opening brackets remain, ensuring that at the end, any remaining stack elements are properly complemented with closing brackets. For each traversed character, appropriate stack operations determine the minimum insertions required.
Complexity
Time Complexity: O(n), due to a single pass through the string.
Space Complexity: O(n), maximum stack space needed for unmatched '('.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Single Pass Counting | Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1), using constant space for variables. |
| Stack-based Analysis | Time Complexity: O(n), due to a single pass through the string. Space Complexity: O(n), maximum stack space needed for unmatched '('. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-based Analysis | O(n) | O(n) | When explaining matching logic step-by-step or adapting classic stack parenthesis validation |
| Single Pass Counting (Greedy) | O(n) | O(1) | Optimal solution for interviews and large inputs due to constant memory |
Video Solution
LeetCode 1541. Minimum Insertions to Balance a Parentheses String - Interview Prep Ep 88 • Fisher Coder • 6,628 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Insertions to Balance a Parentheses String easy or hard?
Minimum Insertions to Balance a Parentheses String Python/Java solution
How to solve Minimum Insertions to Balance a Parentheses String in O(n)?
What is the best approach for Minimum Insertions to Balance a Parentheses String?
Is Minimum Insertions to Balance a Parentheses String asked at Google/Amazon/Meta?
What data structure is used in Minimum Insertions to Balance a Parentheses String?
What is the time complexity of Minimum Insertions to Balance a Parentheses String?
Ready to solve this problem?
Practice Minimum Insertions to Balance a Parentheses String with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor