Minimum Insertions to Balance a Parentheses String solution and explanation
Google
9 more videos on this problem
LeetCode 1541. Minimum Insertions to Balance a Parentheses String - Interview Prep Ep 88Fisher Coder · 17:31 · 6K views
Leetcode 1541: Minimum insertion to balance brackets - Ep6InterviewDose · 11:02 · 2K views
Minimum Insertions to Balance a Parentheses String mix in Hindi || LeetCode Biweekly Contest 32Code With Hemant Dhanuka · 19:20 · 1K views
Biweekly Contest 32 || PROBLEM 1539 , 1540 , 1541 || LEETCODEcode Explainer · 20:26 · 1K views
[Solution] Leetcode 1541: Minimum Insertions to Balance a Parentheses String (Biweekly Contest 32)Daksh Experiments · 8:03 · 923 views
Leetcode 1541. Minimum Insertions to Balance a Parentheses StringAjith S · 9:56 · 882 views
1541. Minimum Insertions to Balance a Parentheses String (Leetcode Medium)Programming Live with Larry · 21:30 · 818 views
[Thinking Out Loud] Leetcode 1541: Minimum Insertions to Balance a Parentheses String (BWContest 32)Daksh Experiments · 18:25 · 285 views
小飞羊 LeetCode 1541. Minimum Insertions to Balance a Parentheses String [套路得人薪C++]Willy小飞羊 DJ · 7:03 · 195 views
LeetCode 1541. Minimum Insertions to Balance a Parentheses Stringbbbb · 9:14 · 98 views
The problem
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.
def minInsertions(s: str) -> int:
left = 0
right_needed = 0
insertions = 0
i = 0
while i < len(s):
if s[i] == '(':
left += 1
else:
if i + 1 < len(s) and s[i + 1] == ')':
# It's a valid '))' sequence
if left > 0:
left -= 1
else:
insertions += 1
i += 1
else:
# Single ')'
if left > 0:
left -= 1
insertions += 1 # Need one more ')'
else:
insertions += 2 # Need '(' and one more ')'
i += 1
insertions += left * 2
return insertionspublic class BalancedParentheses {
public static int minInsertions(String s) {
int left = 0, rightNeeded = 0, insertions = 0;
int i = 0;
while (i < s.length()) {
if (s.charAt(i) == '(') {
left++;
} else {
if (i + 1 < s.length() && s.charAt(i + 1) == ')') {
if (left > 0) left--;
else insertions++;
i++;
} else {
if (left > 0) {
left--;
insertions++;
} else {
insertions += 2;
}
}
}
i++;
}
insertions += left * 2;
return insertions;
}
}#include <string>
using namespace std;
class Solution {
public:
int minInsertions(string s) {
int left = 0, insertions = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') {
left++;
} else {
if (i + 1 < s.size() && s[i + 1] == ')') {
if (left > 0) left--;
else insertions++;
i++;
} else {
if (left > 0) {
left--;
insertions++;
} else {
insertions += 2;
}
}
}
}
insertions += left * 2;
return insertions;
}
};function minInsertions(s) {
let left = 0, insertions = 0;
let i = 0;
while (i < s.length) {
if (s[i] === '(') {
left++;
} else {
if (i + 1 < s.length && s[i + 1] === ')') {
if (left > 0) left--;
else insertions++;
i++;
} else {
if (left > 0) {
left--;
insertions++;
} else {
insertions += 2;
}
}
}
i++;
}
insertions += left * 2;
return insertions;
}#include <stdio.h>
#include <string.h>
int minInsertions(char* s) {
int left = 0, insertions = 0, length = strlen(s);
for (int i = 0; i < length; ++i) {
if (s[i] == '(') {
left++;
} else {
if (i + 1 < length && s[i + 1] == ')') {
if (left > 0) left--;
else insertions++;
i++;
} else {
if (left > 0) {
left--;
insertions++;
} else {
insertions += 2;
}
}
}
}
insertions += left * 2;
return insertions;
}public class Solution {
public int MinInsertions(string s) {
int left = 0, insertions = 0, i = 0;
while (i < s.Length) {
if (s[i] == '(') {
left++;
} else {
if (i + 1 < s.Length && s[i + 1] == ')') {
if (left > 0) left--;
else insertions++;
i++;
} else {
if (left > 0) {
left--;
insertions++;
} else {
insertions += 2;
}
}
}
i++;
}
insertions += left * 2;
return insertions;
}
}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.
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.
def minInsertions(s: str) -> int:
stack = []
insertions = 0
i = 0
while i < len(s):
if s[i] == '(':
stack.append('(')
else:
if i + 1 < len(s) and s[i + 1] == ')':
if stack:
stack.pop()
else:
insertions += 1
i += 1
else:
if stack:
stack.pop()
insertions += 1
else:
insertions += 2
i += 1
insertions += len(stack) * 2
return insertionsimport java.util.Stack;
public class BalancedParentheses {
public static int minInsertions(String s) {
Stack<Character> stack = new Stack<>();
int insertions = 0, i = 0;
while (i < s.length()) {
if (s.charAt(i) == '(') {
stack.push('(');
} else {
if (i + 1 < s.length() && s.charAt(i + 1) == ')') {
if (!stack.isEmpty()) stack.pop();
else insertions++;
i++;
} else {
if (!stack.isEmpty()) {
stack.pop();
insertions++;
} else {
insertions += 2;
}
}
}
i++;
}
insertions += stack.size() * 2;
return insertions;
}
}#include <stack>
#include <string>
using namespace std;
class Solution {
public:
int minInsertions(string s) {
stack<char> stk;
int insertions = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') {
stk.push('(');
} else {
if (i + 1 < s.size() && s[i + 1] == ')') {
if (!stk.empty()) stk.pop();
else insertions++;
i++;
} else {
if (!stk.empty()) {
stk.pop();
insertions++;
} else {
insertions += 2;
}
}
}
}
insertions += stk.size() * 2;
return insertions;
}
};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.
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
func minInsertions(s string) int {
ans, x, n := 0, 0, len(s)
for i := 0; i < n; i++ {
if s[i] == '(' {
x++
} else {
if i < n-1 && s[i+1] == ')' {
i++
} else {
ans++
}
if x == 0 {
ans++
} else {
x--
}
}
}
ans += x << 1
return ans
}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 | – |
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 |
Frequently asked questions
Is Minimum Insertions to Balance a Parentheses String easy or hard?
The problem is classified as Medium because the rule that each '(' must match two ')' changes the standard parentheses validation logic. Recognizing the greedy counting invariant and handling odd closing requirements is the key difficulty.
Minimum Insertions to Balance a Parentheses String Python/Java solution
Most implementations follow the greedy counter approach. Maintain variables for insertions and required closing parentheses, iterate through the string, and update the counts based on whether the current character is '(' or ')'. This implementation translates directly to Python, Java, C++, and JavaScript with identical O(n) complexity.
How to solve Minimum Insertions to Balance a Parentheses String in O(n)?
Traverse the string while maintaining a counter for required closing parentheses. Each '(' increases the requirement by two, while ')' decreases it. If the requirement becomes odd, insert a closing parenthesis; if it becomes negative, insert an opening one. This greedy adjustment guarantees correctness in a single linear scan.
What is the best approach for Minimum Insertions to Balance a Parentheses String?
The greedy single-pass counting approach is the best solution. It scans the string once while tracking how many closing parentheses are still required. The algorithm runs in O(n) time and uses O(1) space, making it more efficient than stack-based simulations.
Is Minimum Insertions to Balance a Parentheses String asked at Google/Amazon/Meta?
Parentheses balancing and string parsing problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test greedy reasoning, stack usage, and the ability to maintain invariants during a single pass through a string.
What data structure is used in Minimum Insertions to Balance a Parentheses String?
Two common approaches exist. A stack can simulate matching parentheses and track unmatched '(' characters. The optimal solution avoids extra data structures and instead uses greedy counting with simple integer variables.
What is the time complexity of Minimum Insertions to Balance a Parentheses String?
The optimal solution runs in O(n) time because the string is scanned exactly once. Each character updates counters or insertion counts in constant time. Space complexity is O(1) when using the greedy counting method.