921. Minimum Add to Make Parentheses Valid
Minimum Add to Make Parentheses Valid (LeetCode 921) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Valid Parentheses Matching subpattern.
How to solve Minimum Add to Make Parentheses Valid
Minimum Add to Make Parentheses Valid is a Valid Parentheses problem, part of Stack Patterns. Master parentheses validation and balancing using stack. Handle multiple bracket types and minimum additions.
Work towards the solution in these steps:
- Consider using a stack to keep track of parentheses while scanning through the string to identify mismatches.
- Think about how pushing opening parentheses and popping when encountering closing ones can help detect invalid pairs.
- Observe what happens when you encounter a closing parenthesis but the stack is empty — this indicates an unmatched closing parenthesis.
The reference solution runs in O(n) time and O(1) space.
The Minimum Add to Make Parentheses Valid solution and editorial walks through the full approach with reference code.
Problem statement
A parentheses string is valid if and only if:
- It is the empty string,
- It can be written as AB (A concatenated with B), where A and B are valid strings, or
- It can be written as (A), where A is a valid string.
You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
- For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".
Return the minimum number of moves required to make s valid.
Example 1:
Input: s = "())" Output: 1
Example 2:
Input: s = "(((" Output: 3
Constraints:
- 1 <= s.length <= 1000
- s[i] is either '(' or ')'.
Topics and companies
Topics: String, Stack, Greedy.
Reported in interviews at Facebook, Visa.
How to practise Minimum Add to Make Parentheses Valid on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Minimum Add to Make Parentheses Valid in the code editor, or read the Minimum Add to Make Parentheses Valid editorial for a worked solution with its approach and complexity analysis.
Where Minimum Add to Make Parentheses Valid sits in the DSA pattern sheet
Problems related to Minimum Add to Make Parentheses Valid
Other problems that use the same Valid Parentheses Matching and Stack Patterns techniques:
- Longest Valid Parentheses — Hard, same subpattern
- Minimum Number of Swaps to Make the String Balanced — Medium, same subpattern
- Minimum Remove to Make Valid Parentheses — Medium, same subpattern
- Valid Parentheses — Easy, same subpattern
- Valid Parenthesis String — Medium, same subpattern
- Asteroid Collision — Medium, same pattern
Minimum Add to Make Parentheses Valid FAQ
What is the LeetCode number of Minimum Add to Make Parentheses Valid?
Minimum Add to Make Parentheses Valid is LeetCode problem 921, rated Medium.
What pattern is used to solve Minimum Add to Make Parentheses Valid?
Minimum Add to Make Parentheses Valid is a Valid Parentheses problem. It belongs to the Stack Patterns pattern, in the Valid Parentheses Matching subpattern.
What is the time complexity of Minimum Add to Make Parentheses Valid?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Minimum Add to Make Parentheses Valid?
Minimum Add to Make Parentheses Valid has been reported in interviews at Facebook, Visa.