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.
1#include <stdbool.h>
2#include <stdio.h>
3#include <string.h>
4
5bool isValid(char * s) {
6 char stack[strlen(s)];
7 int top = -1;
8 for (int i = 0; s[i]; i++) {
9 char c = s[i];
10 if (c == '(' || c == '{' || c == '[') {
11 stack[++top] = c;
12 } else {
13 if (top == -1) return false;
14 char topChar = stack[top--];
15 if ((c == ')' && topChar != '(') ||
16 (c == '}' && topChar != '{') ||
17 (c == ']' && topChar != '['))
18 return false;
19 }
20 }
21 return top == -1;
22}
23
24int main() {
25 printf("%d\n", isValid("()[]{}")); // Output: 1 (true)
26 printf("%d\n", isValid("(]")); // Output: 0 (false)
27 return 0;
28}This C program uses an array stack to store opening brackets. It checks each character from left to right, pushing opening brackets onto the stack and popping it to match with corresponding closing brackets. If a mismatch is found or the stack isn't empty at the end, it returns false.
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.
This C solution strategically checks potential stack overflow and underflow using an array pointer technique, relying on an indexing control within the allowed stack-size limits. Each mismatched pair check ensures parentheses are properly closed.