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 '()[]{}'.Problem Overview: Given a string containing characters ()[]{}, determine if the parentheses are valid. A string is valid when every opening bracket has a matching closing bracket of the same type and the pairs are closed in the correct order.
This problem appears simple but tests your understanding of stack behavior and sequential validation in a string. The core challenge is ensuring that the most recently opened bracket is the first one that must close.
Approach 1: Stack-Based Approach (O(n) time, O(n) space)
The standard solution uses a stack to track opening brackets as you iterate through the string. When you encounter an opening bracket ((, [, {), push it onto the stack. When you see a closing bracket, check the top of the stack to confirm it matches the corresponding opening type. If it matches, pop the stack; otherwise the string is invalid.
The key insight is that brackets must close in reverse order of opening. A stack naturally enforces this Last-In-First-Out behavior. At the end of the iteration, the stack must be empty for the string to be valid. This approach processes each character once, giving O(n) time complexity with O(n) auxiliary space in the worst case when all characters are opening brackets.
Approach 2: Two Pointer Approach with Stack-Like Behavior (O(n) time, O(n) space)
This variation simulates stack behavior using pointer movement and an array-like buffer instead of an explicit stack structure. As you iterate through the string, use one pointer as a "top" index where opening brackets are stored. When a closing bracket appears, compare it against the element at the top pointer and decrement the pointer if it matches.
The logic mirrors stack push and pop operations but uses pointer arithmetic instead of a dedicated stack container. This can slightly reduce overhead in lower-level languages and demonstrates how stack mechanics can be implemented directly with arrays or pointer indices. Each character is still processed once, resulting in O(n) time complexity and up to O(n) space for storing unmatched opening brackets.
Recommended for interviews: The stack-based solution is what most interviewers expect. It clearly demonstrates understanding of stack operations and bracket matching logic. A brute-force validation would quickly become complex with nested pairs, while the stack approach solves the problem cleanly in linear time. Knowing how to implement the same logic with a pointer-backed array is a useful follow-up optimization discussion.
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).
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.
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.
This approach uses two pointers with stack-like behavior internally, taking advantage of simple list operations for push and pop.
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.
Time Complexity: O(n)
Space Complexity: O(n/2) = O(n)
Traverse the bracket string s. When encountering a left bracket, push the current left bracket into the stack; when encountering a right bracket, pop the top element of the stack (if the stack is empty, directly return false), and judge whether it matches. If it does not match, directly return false.
Alternatively, when encountering a left bracket, you can push the corresponding right bracket into the stack; when encountering a right bracket, pop the top element of the stack (if the stack is empty, directly return false), and judge whether they are equal. If they do not match, directly return false.
The difference between the two methods is only the timing of bracket conversion, one is when pushing into the stack, and the other is when popping out of the stack.
At the end of the traversal, if the stack is empty, it means the bracket string is valid, return true; otherwise, return false.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the bracket string s.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Ruby
PHP
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n), where n is the length of the string, since we process each character once. |
| Two Pointer Approach (with a stack-like behavior) | Time Complexity: O(n) |
| Stack | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Approach | O(n) | O(n) | General solution. Clean and easy to explain in interviews. |
| Two Pointer (Stack Simulation) | O(n) | O(n) | When implementing stack logic with arrays or minimizing stack abstraction overhead. |
Valid Parentheses - Stack - Leetcode 20 - Python • NeetCode • 585,834 views views
Watch 9 more video solutions →Practice Valid Parentheses with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor