20. Valid Parentheses
Valid Parentheses (LeetCode 20) is a Easy 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 Valid Parentheses
Valid Parentheses 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:
- Use a stack of characters.
- When you encounter an opening bracket, push it to the top of the stack.
- When you encounter a closing bracket, check if the top of the stack was the opening for it. If yes, pop it from the stack. Otherwise, return false.
The reference solution runs in O(n) time and O(n) space.
The Valid Parentheses solution and editorial walks through the full approach with reference code.
Problem statement
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([])"
Output: true
Constraints:
- 1 <= s.length <= 104
- s consists of parentheses only '()[]{}'.
Topics and companies
Topics: String, Stack.
Reported in interviews at Amazon, Bloomberg, Facebook, Apple, Microsoft, Expedia, Spotify, Google, LinkedIn, Goldman Sachs, Oracle, IBM and others.
How to practise Valid Parentheses 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(n) space.
Open Valid Parentheses in the code editor, or read the Valid Parentheses editorial for a worked solution with its approach and complexity analysis.
Where Valid Parentheses sits in the DSA pattern sheet
Problems related to Valid Parentheses
Other problems that use the same Valid Parentheses Matching and Stack Patterns techniques:
- Longest Valid Parentheses — Hard, same subpattern
- Minimum Add to Make Parentheses Valid — Medium, same subpattern
- Minimum Number of Swaps to Make the String Balanced — Medium, same subpattern
- Minimum Remove to Make Valid Parentheses — Medium, same subpattern
- Valid Parenthesis String — Medium, same subpattern
- Asteroid Collision — Medium, same pattern
Valid Parentheses FAQ
What is the LeetCode number of Valid Parentheses?
Valid Parentheses is LeetCode problem 20, rated Easy.
What pattern is used to solve Valid Parentheses?
Valid Parentheses is a Valid Parentheses problem. It belongs to the Stack Patterns pattern, in the Valid Parentheses Matching subpattern.
What is the time complexity of Valid Parentheses?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Valid Parentheses?
Valid Parentheses has been reported in interviews at Amazon, Bloomberg, Facebook, Apple, Microsoft, Expedia, Spotify, Google, LinkedIn, Goldman Sachs, Oracle, IBM and others.