Valid Parentheses
Problem Description:
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
Explanation: The brackets are correctly paired and nested.
Example 2:
Input: s = "()[]{}"
Output: true
Explanation: All brackets are correctly paired and in order.
Example 3:
Input: s = "(]"
Output: false
Explanation: The brackets are mismatched, '(' should have ')' and '[' should be there for ']'.
Example 4:
Input: s = "([])"
Output: true
Explanation: The brackets are correctly nested.
Constraints:
1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.
Brute Force Approach
Okay, what comes to our mind after reading the problem statement?
We need to check for every type of closing bracket, there exists an opening bracket of the same type in the correct order.
So let's check for every closing bracket to see whether there's an opening bracket or not, if there exists a closing bracket of the same type in the correct order, we will check for the next element, otherwise, we'll return false.
At the end, we will ensure that each element has a valid pair, and if not we'll return false else we'll return true.
How can we do that?
To determine if the string of brackets is valid, we followed a step-by-step process:
- As we go through each character, we check if it's an opening or a closing bracket.
- When we encounter a closing bracket (like ), ], or }), we look backward to find the nearest matching opening bracket (like (, [, or {). This ensures that every closing bracket is correctly paired with the right type of opening bracket in the right order.
- Once we find a valid pair, we mark them as "visited" so they aren't considered again when processing the rest of the string.
- At the end of the process, if we find any brackets that haven’t been paired, the string isn’t valid.
- If every bracket has been correctly matched and paired, we know the string is valid; otherwise, it’s not.
It’s essentially a careful check to ensure that all opening and closing brackets match perfectly in both type and order.
Let's understand with an example:
Example Walkthrough: s = "([]){()}"
- Start with the first character: '('
'(' is an opening bracket, so we wait for its matching closing bracket. - Next character: '['
'[' is an opening bracket, so we wait for its matching closing bracket. - Next character: ']'
']' is a closing bracket, and it matches '['. Pair them. - Next character: ')'
')' is a closing bracket, and it matches '('. Pair them. - Next character: '{'
'{' is an opening bracket, so we wait for its matching closing bracket. - Next character: '('
'(' is an opening bracket, so we wait for its matching closing bracket. - Next character: ')'
')' is a closing bracket, and it matches '('. Pair them. - Final character: '}'
'}' is a closing bracket, and it matches '{'. Pair them.
Result: All brackets are correctly paired in the right order, so the string is valid. Output: true.
How to code it up:
- Create a vector or array to keep track of visited positions in the string. Each position will indicate whether a bracket has been paired already.
- Iterate through each character in the string and check if it’s a closing bracket (')', ']', or '}').
- If you find a closing bracket, look backward in the string to find the nearest corresponding opening bracket ('(', '{', or '[').
- For each closing bracket, start from the current index and check previous elements until:
- A matching, unpaired opening bracket is found.
- If no matching opening bracket is found or if the matching bracket has already been paired, return false immediately.
- When a match is found, mark both the opening and closing brackets as visited to ensure they won’t be checked again.
- After processing the entire string, ensure all brackets are marked as visited. If any bracket remains unvisited, return false.
- If all brackets have been paired correctly, return true as the result.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
bool isValid(string s) {
int n = s.length();
// Track whether a bracket has been paired already
vector<bool> visited(n, false);
// Loop through each character in the string
for (int i = 0; i < n; i++) {
// Process closing brackets one by one
if (s[i] == ')') {
int j = i - 1;
bool isMatched = false;
// Search for a matching opening bracket '(' before the current closing bracket ')'
while (j >= 0) {
// Check for an unvisited '('
if (visited[j] == false && s[j] == '(') {
isMatched = true;
// Mark the opening bracket as visited
visited[j] = true;
// Mark the closing bracket as visited
visited[i] = true;
break;
}
// If an unmatched bracket is found, return false
if (visited[j] == false)
return false;
j--;
}
// If no matching opening bracket was found, return false
if (!isMatched)
return false;
}
else if (s[i] == ']') {
int j = i - 1;
bool isMatched = false;
// Search for a matching opening bracket '[' before the current closing bracket ']'
while (j >= 0) {
// Check for an unvisited '['
if (visited[j] == false && s[j] == '[') {
isMatched = true;
// Mark the opening bracket as visited
visited[j] = true;
// Mark the closing bracket as visited
visited[i] = true;
break;
}
// If an unmatched bracket is found, return false
if (visited[j] == false)
return false;
j--;
}
// If no matching opening bracket was found, return false
if (!isMatched)
return false;
}
else if (s[i] == '}') {
int j = i - 1;
bool isMatched = false;
// Search for a matching opening bracket '{' before the current closing bracket '}'
while (j >= 0) {
// Check for an unvisited '{'
if (visited[j] == false && s[j] == '{') {
isMatched = true;
// Mark the opening bracket as visited
visited[j] = true;
// Mark the closing bracket as visited
visited[i] = true;
break;
}
// If an unmatched bracket is found, return false
if (visited[j] == false)
return false;
j--;
}
// If no matching opening bracket was found, return false
if (!isMatched)
return false;
}
}
// Final check to ensure all brackets have been visited (paired)
for (int i = 0; i < n; i++) {
// If any bracket hasn't been visited, return false
if (!visited[i])
return false;
}
// All brackets are properly paired
return true;
}
};
2. Java Try on Compiler
class Solution {
public boolean isValid(String s) {
int n = s.length();
// Track whether a bracket has been paired already
boolean[] visited = new boolean[n];
// Loop through each character in the string
for (int i = 0; i < n; i++) {
// Process closing brackets one by one
if (s.charAt(i) == ')') {
int j = i - 1;
boolean isMatched = false;
// Search for a matching opening bracket '(' before the current closing bracket ')'
while (j >= 0) {
// Check for an unvisited '('
if (!visited[j] && s.charAt(j) == '(') {
isMatched = true;
// Mark the opening bracket as visited
visited[j] = true;
// Mark the closing bracket as visited
visited[i] = true;
break;
}
// If an unmatched bracket is found, return false
if (!visited[j])
return false;
j--;
}
// If no matching opening bracket was found, return false
if (!isMatched)
return false;
} else if (s.charAt(i) == ']') {
int j = i - 1;
boolean isMatched = false;
// Search for a matching opening bracket '[' before the current closing bracket ']'
while (j >= 0) {
// Check for an unvisited '['
if (!visited[j] && s.charAt(j) == '[') {
isMatched = true;
// Mark the opening bracket as visited
visited[j] = true;
// Mark the closing bracket as visited
visited[i] = true;
break;
}
// If an unmatched bracket is found, return false
if (!visited[j])
return false;
j--;
}
// If no matching opening bracket was found, return false
if (!isMatched)
return false;
} else if (s.charAt(i) == '}') {
int j = i - 1;
boolean isMatched = false;
// Search for a matching opening bracket '{' before the current closing bracket '}'
while (j >= 0) {
// Check for an unvisited '{'
if (!visited[j] && s.charAt(j) == '{') {
isMatched = true;
// Mark the opening bracket as visited
visited[j] = true;
// Mark the closing bracket as visited
visited[i] = true;
break;
}
// If an unmatched bracket is found, return false
if (!visited[j])
return false;
j--;
}
// If no matching opening bracket was found, return false
if (!isMatched)
return false;
}
}
// Final check to ensure all brackets have been visited (paired)
for (int i = 0; i < n; i++) {
// If any bracket hasn't been visited, return false
if (!visited[i])
return false;
}
// All brackets are properly paired
return true;
}
}
3. Python Try on Compiler
class Solution:
def isValid(self, s):
n = len(s)
# Track whether a bracket has been paired already
visited = [False] * n
# Loop through each character in the string
for i in range(n):
# Process closing brackets one by one
if s[i] == ')':
j = i - 1
isMatched = False
# Search for a matching opening bracket '(' before the current closing bracket ')'
while j >= 0:
# Check for an unvisited '('
if not visited[j] and s[j] == '(':
isMatched = True
# Mark the opening bracket as visited
visited[j] = True
# Mark the closing bracket as visited
visited[i] = True
break
# If an unmatched bracket is found, return false
if not visited[j]:
return False
j -= 1
# If no matching opening bracket was found, return false
if not isMatched:
return False
elif s[i] == ']':
j = i - 1
isMatched = False
# Search for a matching opening bracket '[' before the current closing bracket ']'
while j >= 0:
# Check for an unvisited '['
if not visited[j] and s[j] == '[':
isMatched = True
# Mark the opening bracket as visited
visited[j] = True
# Mark the closing bracket as visited
visited[i] = True
break
# If an unmatched bracket is found, return false
if not visited[j]:
return False
j -= 1
# If no matching opening bracket was found, return false
if not isMatched:
return False
elif s[i] == '}':
j = i - 1
isMatched = False
# Search for a matching opening bracket '{' before the current closing bracket '}'
while j >= 0:
# Check for an unvisited '{'
if not visited[j] and s[j] == '{':
isMatched = True
# Mark the opening bracket as visited
visited[j] = True
# Mark the closing bracket as visited
visited[i] = True
break
# If an unmatched bracket is found, return false
if not visited[j]:
return False
j -= 1
# If no matching opening bracket was found, return false
if not isMatched:
return False
# Final check to ensure all brackets have been visited (paired)
for i in range(n):
# If any bracket hasn't been visited, return false
if not visited[i]:
return False
# All brackets are properly paired
return True
4. Javascript Try on Compiler
var isValid = function(s) {
const n = s.length;
// Track whether a bracket has been paired already
let visited = new Array(n).fill(false);
// Loop through each character in the string
for (let i = 0; i < n; i++) {
// Process closing brackets one by one
if (s[i] === ')') {
let j = i - 1;
let isMatched = false;
// Search for a matching opening bracket '(' before the current closing bracket ')'
while (j >= 0) {
// Check for an unvisited '('
if (!visited[j] && s[j] === '(') {
isMatched = true;
// Mark the opening bracket as visited
visited[j] = true;
// Mark the closing bracket as visited
visited[i] = true;
break;
}
// If an unmatched bracket is found, return false
if (!visited[j]) {
return false;
}
j--;
}
// If no matching opening bracket was found, return false
if (!isMatched) {
return false;
}
} else if (s[i] === ']') {
let j = i - 1;
let isMatched = false;
// Search for a matching opening bracket '[' before the current closing bracket ']'
while (j >= 0) {
// Check for an unvisited '['
if (!visited[j] && s[j] === '[') {
isMatched = true;
// Mark the opening bracket as visited
visited[j] = true;
// Mark the closing bracket as visited
visited[i] = true;
break;
}
// If an unmatched bracket is found, return false
if (!visited[j]) {
return false;
}
j--;
}
// If no matching opening bracket was found, return false
if (!isMatched) {
return false;
}
} else if (s[i] === '}') {
let j = i - 1;
let isMatched = false;
// Search for a matching opening bracket '{' before the current closing bracket '}'
while (j >= 0) {
// Check for an unvisited '{'
if (!visited[j] && s[j] === '{') {
isMatched = true;
// Mark the opening bracket as visited
visited[j] = true;
// Mark the closing bracket as visited
visited[i] = true;
break;
}
// If an unmatched bracket is found, return false
if (!visited[j]) {
return false;
}
j--;
}
// If no matching opening bracket was found, return false
if (!isMatched) {
return false;
}
}
}
// Final check to ensure all brackets have been visited (paired)
for (let i = 0; i < n; i++) {
// If any bracket hasn't been visited, return false
if (!visited[i]) {
return false;
}
}
// All brackets are properly paired
return true;
};
Time Complexity: O(n²)
The outer loop processes each character in the input string exactly once. For a string of length n, this loop iterates n times.
For each closing bracket, the algorithm searches backward for the matching opening bracket. In the worst-case scenario, the inner loop might need to traverse through all previous characters, leading to potential i iterations for a closing bracket at position i.
The total operations performed by the inner loop can be expressed as the sum of operations across all outer loop iterations:
Total operations = 0 + 1 + 2 + 3 + ... + (n-1)
This is the sum of the first n-1 integers, which is given by the formula:
Sum = n(n-1)/2
In Big-O notation, considering only the dominant term, we get: O(n²)
The outer loop runs n times, and for each closing bracket, the inner loop could potentially run in O(n) time. Therefore, the overall time complexity due to the nested operations is: O(n²)
The worst-case time complexity of this algorithm is O(n²), primarily due to the inner loop's potential to check all previous characters for matching brackets.
Space Complexity: O(n)
Auxiliary Space: O(n)
Explanation: The only additional data structure used in the solution is the visited array, which tracks whether a bracket has been paired or not.
This array has a size of n (the length of the input string s) because we mark each character in the string to track whether it has been paired.
Thus, the auxiliary space is O(n) because of this extra visited array.
Total Space: O(n)
Explanation: The input string s itself occupies space proportional to its length, which is O(n). The visited array also occupies O(n) space.
Therefore, the total space used by the algorithm is O(n).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is suitable for n ≤ 10⁴. This means that for each test case the length of string is at most 10⁴, the solution should execute within the given time limits.
Since O(n²) results in a maximum of 10⁸ operations (for n = 10⁴), the solution is expected to work well for individual test cases under these constraints, typically allowing around 1–2 seconds for execution.
In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning for n ≤ 10⁴, the solution is efficient enough. However, when multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10⁸ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Can we optimize it?
In our earlier implementation, we processed the input string in a reverse manner whenever we encountered a closing bracket. This was done to find its corresponding opening bracket of the same type in the correct sequence.
By moving backward, we ensured that the nested or matched brackets were properly identified before proceeding to the next steps of the solution.
This approach, while functional, involved additional overhead in traversing the string multiple times, potentially leading to inefficiencies in cases with deeply nested or numerous brackets.
But what if we don't need to traverse back the entire string to find the suitable opening bracket for a closing bracket?
What if we only store the relevant brackets for every step?
Suppose we encounter a closing bracket ')'. Now, to check if the parentheses are valid, we need to ensure there is a '(' for it in the correct order. So, whenever we encounter a closing bracket, we need to find its corresponding opening bracket.
To achieve this, we can store all opening brackets one by one whenever we encounter them. If we find a closing bracket, we remove its matching opening bracket and keep both of them aside as the pair is completed.
Similarly, we check for other pairs as well. If we encounter another type of opening bracket that doesn't match, we simply return false. If all pairs are valid by the end of the process, we return true.
Basically, we want to compare our current closing bracket with the last opening bracket encountered. So we need to store our last opening bracket in a data structure where we can push our opening brackets sequentially to maintain correct order, can compare our last opening bracket with the current closing bracket, and can pop out the last opening bracket whenever we want.
Wait!! isn't it similar to Last In, First Out (LIFO)??
Which data structure can help us here?
Yes, you're right!
Since we need to keep track of the last opening bracket, we can use a stack. Whenever we find a closing bracket, we check the stack's top to see if there's a valid match. If yes, we pop it and move ahead. If not, we return false.
What is a stack?
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. You can think of it like a stack of plates where you add and remove plates from the top.
Using this approach we can efficiently find if a string is valid or not.
Example Dry Run:
Input string: {([])}
Step 1:
Character: '{' → It's an opening bracket. Push onto the stack.
Stack: ['{']
Step 2:
Character: '(' → It's an opening bracket. Push onto the stack.
Stack: ['{', '(']
Step 3:
Character: '[' → It's an opening bracket. Push onto the stack.
Stack: ['{', '(', '[']
Step 4:
Character: ']' → It's a closing bracket. Check the top of the stack: [ matches ]. Pop the top.
Stack: ['{', '(']
Step 5:
Character: ')' → It's a closing bracket. Check the top of the stack: ( matches ). Pop the top.
Stack: ['{']
Step 6:
Character: '}' → It's a closing bracket. Check the top of the stack: { matches }. Pop the top.
Stack: []
Final State:
Stack: [] (empty, all pairs matched)
Result: Valid (return true)
Let's understand with visuals
How to code it up:
Initialize a stack:
- Use the stack to store opening brackets as they appear in the string.
Iterate through the characters of the string (for loop):
- Check each character:
- If it's a closing bracket, ensure the stack's top has the corresponding opening bracket:
- If the stack is empty or the top of the stack doesn't match, return false.
- Otherwise, pop the top of the stack (since the pair is valid).
- If it's an opening bracket, push it onto the stack.
After iteration:
- If the stack is empty, return true (all brackets were matched correctly).
- If the stack is not empty, return false (some unmatched opening brackets remain).
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
bool isValid(string s) {
// Initialize a stack to store opening brackets
stack<char> st;
// Iterate through the characters in the string
for (auto ch : s) {
if (ch == ')') {
// If it's a closing parenthesis
if (st.empty() || st.top() != '(')
// Mismatch or no opening parenthesis
return false;
// Pop the matched opening parenthesis
st.pop();
}
else if (ch == '}') {
// If it's a closing curly bracket
if (st.empty() || st.top() != '{')
// Mismatch or no opening curly bracket
return false;
// Pop the matched opening curly bracket
st.pop();
}
else if (ch == ']') {
// If it's a closing square bracket
if (st.empty() || st.top() != '[')
// Mismatch or no opening square bracket
return false;
// Pop the matched opening square bracket
st.pop();
}
else {
// If it's an opening bracket, push it onto the stack
st.push(ch);
}
}
// If the stack is empty, all brackets are matched
return st.empty();
}
};2. Java Try on Compiler
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
// Initialize a stack to store opening brackets
Stack<Character> st = new Stack<>();
// Iterate through the characters in the string
for (char ch : s.toCharArray()) {
if (ch == ')') {
// If it's a closing parenthesis
if (st.isEmpty() || st.peek() != '(')
// Mismatch or no opening parenthesis
return false;
// Pop the matched opening parenthesis
st.pop();
}
else if (ch == '}') {
// If it's a closing curly bracket
if (st.isEmpty() || st.peek() != '{')
// Mismatch or no opening curly bracket
return false;
// Pop the matched opening curly bracket
st.pop();
}
else if (ch == ']') {
// If it's a closing square bracket
if (st.isEmpty() || st.peek() != '[')
// Mismatch or no opening square bracket
return false;
// Pop the matched opening square bracket
st.pop();
}
else {
// If it's an opening bracket, push it onto the stack
st.push(ch);
}
}
// If the stack is empty, all brackets are matched
return st.isEmpty();
}
}
3. Python Try on Compiler
class Solution:
def isValid(self, s):
# Initialize a stack to store opening brackets
st = []
# Iterate through the characters in the string
for ch in s:
if ch == ')':
# If it's a closing parenthesis
if not st or st[-1] != '(':
# Mismatch or no opening parenthesis
return False
# Pop the matched opening parenthesis
st.pop()
elif ch == '}':
# If it's a closing curly bracket
if not st or st[-1] != '{':
# Mismatch or no opening curly bracket
return False
# Pop the matched opening curly bracket
st.pop()
elif ch == ']':
# If it's a closing square bracket
if not st or st[-1] != '[':
# Mismatch or no opening square bracket
return False
# Pop the matched opening square bracket
st.pop()
else:
# If it's an opening bracket, push it onto the stack
st.append(ch)
# If the stack is empty, all brackets are matched
return not st
4. Javascript Try on Compiler
var isValid = function(s) {
// Initialize a stack to store opening brackets
const st = [];
// Iterate through the characters in the string
for (const ch of s) {
if (ch === ')') {
// If it's a closing parenthesis
if (st.length === 0 || st[st.length - 1] !== '(')
// Mismatch or no opening parenthesis
return false;
// Pop the matched opening parenthesis
st.pop();
}
else if (ch === '}') {
// If it's a closing curly bracket
if (st.length === 0 || st[st.length - 1] !== '{')
// Mismatch or no opening curly bracket
return false;
// Pop the matched opening curly bracket
st.pop();
}
else if (ch === ']') {
// If it's a closing square bracket
if (st.length === 0 || st[st.length - 1] !== '[')
// Mismatch or no opening square bracket
return false;
// Pop the matched opening square bracket
st.pop();
}
else {
// If it's an opening bracket, push it onto the stack
st.push(ch);
}
}
// If the stack is empty, all brackets are matched
return st.length === 0;
}Time Complexity: O(n)
The algorithm iterates through each character in the string exactly once. This contributes O(n) to the time complexity.
Each character is processed exactly once during traversal of the string. It can either be pushed onto the stack or popped from the stack, so each character is involved in two operations at most (push and pop).
However, since push and pop operations are constant-time operations O(1), the total number of operations for all characters is still linear with respect to the size of the input string.
Thus, the overall time complexity remains O(n), even though each character is processed twice. The operations are not nested, so the complexity is not squared.
Space Complexity: O(n)
Auxiliary Space: O(n)
Explanation: In this solution, the only extra space used is the stack. At most, the stack will hold all the opening brackets in the string. In the worst case, the string consists only of opening brackets, in which case the stack will hold all n characters.
Therefore, the auxiliary space used by the stack is O(n), where n is the length of the string.
Total Space: O(n)
Explanation: The total space complexity is O(n) because the space required for the stack and the input string is in the same order of magnitude.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the ith asteroid.
You can arrange for the planet to collide with the asteroids in any arbitrary order. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed.
Return true if all asteroids can be destroyed. Otherwise, return false.
You are given n 1-indexed robots, each having a position on a line, health, and movement direction.
You are given 0-indexed integer arrays positions, healths, and a string directions (directions[i] is either 'L' for left or 'R' for right). All integers in positions are unique.
All robots start moving on the line simultaneously at the same speed in their given directions. If two robots ever share the same position while moving, they will collide.
If two robots collide, the robot with lower health is removed from the line, and the health of the other robot decreases by one. The surviving robot continues in the same direction it was going. If both robots have the same health, they are both removed from the line.
Your task is to determine the health of the robots that survive the collisions, in the same order that the robots were given, i.e., final health of robot 1 (if survived), final health of robot 2 (if survived), and so on. If there are no survivors, return an empty array.
Return an array containing the health of the remaining robots (in the order they were given in the input), after no further collisions can occur.
Note: The positions may be unsorted.