Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
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 <= 104s consists of parentheses only '()[]{}'.The Valid Parentheses problem asks whether a string of brackets like (), {}, and [] is properly balanced. The key observation is that every closing bracket must match the most recent unmatched opening bracket.
A common approach is to use a stack. As you iterate through the string, push opening brackets onto the stack. When a closing bracket appears, check the top of the stack to see if it forms a valid pair. If it does, remove the opening bracket; otherwise, the string is invalid. This method works because stacks follow the Last-In-First-Out (LIFO) principle, which mirrors how nested parentheses behave.
After processing the entire string, the sequence is valid only if the stack is empty. This approach efficiently validates bracket order and nesting while scanning the string once. The algorithm runs in O(n) time with up to O(n) additional space for the stack.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based validation | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
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.
This approach uses a stack to efficiently match opening and closing brackets. The stack stores opening brackets, and for each closing bracket encountered, it checks if it closes the last opened bracket (top of the stack).
Time Complexity: O(n), where n is the length of the string, since we process each character once.
Space Complexity: O(n) in the worst case if the string consists only of opening brackets.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public bool IsValid(string s) {
6 Stack<char> stack = new Stack<char>();
7 foreach (char c in s) {
8 if (c == '(' || c == '{' || c == '[') {
9 stack.Push(c);
10 } else {
11 if (stack.Count == 0) return false;
12 char top = stack.Pop();
13 if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '['))
return false;
}
}
return stack.Count == 0;
}
}
public class Program {
public static void Main() {
var solution = new Solution();
Console.WriteLine(solution.IsValid("()[]{}")); // Output: True
Console.WriteLine(solution.IsValid("(]")); // Output: False
}
}The C# solution uses a stack to evaluate valid sequences of parentheses, brackets, and braces. The use of a stack simplifies checking against preceding open brackets.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Valid Parentheses is a very common interview question and frequently appears in FAANG-style coding interviews. It tests fundamental knowledge of stacks, string traversal, and problem-solving patterns used in many parsing problems.
A stack is the most suitable data structure for this problem because it follows the Last-In-First-Out principle. This property naturally matches how nested parentheses work, where the most recent opening bracket must be closed first.
The optimal approach uses a stack to track opening brackets while scanning the string. When a closing bracket appears, it must match the most recent opening bracket on the stack. This allows the problem to be solved in linear time with a single pass through the string.
The stack approach works because each closing bracket must correspond to the most recent unmatched opening bracket. By pushing opening brackets and popping them when a matching closing bracket appears, the algorithm ensures correct order and nesting.
In Java, using StringBuilder along with character matching achieves similar stack manipulation while maintaining easy removability and appendability onto the existing stack representation.