Valid Parentheses solution and explanation
IBM
Nokia
9 more videos on this problem
Valid Parentheses - Stack - Leetcode 20 - PythonNeetCode · 10:43 · 613K views
LeetCode 20. Valid Parentheses Solution Explained - JavaNick White · 7:28 · 88K views
Valid Parentheses (LeetCode 20) | Full solution with visuals and animations | Stack Data StructureNikhil Lohia · 15:01 · 54K views
Valid Parentheses - Leetcode 20 - Stacks (Python)Greg Hogg · 8:55 · 33K views
LeetCode 20: Valid Parentheses | Stack Data StructureAbstracted Away · 5:44 · 25K views
Valid Parentheses - Stack - C++ - Leetcode 20ProgrammingKnowledge · 8:25 · 7K views
Valid Parentheses - LeetCode 20 - JavaScriptAlgoJS · 6:50 · 6K views
20. Valid Parentheses | LeetCode | TypeScriptAbdul Rahman · 15:12 · 2K views
Valid Parentheses - LeetCode 20 - Java | StackLeetCode University · 19:17 · 2K views
Valid Parentheses Python Solution - LeetCode #20Professor Oakes · 4:39 · 1K views
The problem
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 <= 104sconsists of parentheses only'()[]{}'.
Approach overview
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.
Approach 1: Stack-Based Approach
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).
def isValid(s: str) -> bool:
stack = []
mapping = {
')': '(',
'}': '{',
']': '['
}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stackimport java.util.Stack;
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '['))
return false;
}
}
return stack.isEmpty();
}
}#include <stack>
#include <string>
bool isValid(std::string s) {
std::stack<char> stack;
for (char& c : s) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.empty()) return false;
char top = stack.top();
stack.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '['))
return false;
}
}
return stack.empty();
}function isValid(s) {
const stack = [];
const map = {
')': '(',
'}': '{',
']': '['
};
for (const char of s) {
if (map[char]) {
if (stack.pop() !== map[char]) {
return false;
}
} else {
stack.push(char);
}
}
return stack.length === 0;
}
console.log(isValid("()[]{}")); // Output: true
console.log(isValid("(]")); // Output: false#include <stdbool.h>
#include <stdio.h>
#include <string.h>
bool isValid(char * s) {
char stack[strlen(s)];
int top = -1;
for (int i = 0; s[i]; i++) {
char c = s[i];
if (c == '(' || c == '{' || c == '[') {
stack[++top] = c;
} else {
if (top == -1) return false;
char topChar = stack[top--];
if ((c == ')' && topChar != '(') ||
(c == '}' && topChar != '{') ||
(c == ']' && topChar != '['))
return false;
}
}
return top == -1;
}
int main() {
printf("%d\n", isValid("()[]{}")); // Output: 1 (true)
printf("%d\n", isValid("(]")); // Output: 0 (false)
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public bool IsValid(string s) {
Stack<char> stack = new Stack<char>();
foreach (char c in s) {
if (c == '(' || c == '{' || c == '[') {
stack.Push(c);
} else {
if (stack.Count == 0) return false;
char top = stack.Pop();
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
}
}This Python function utilizes a list as a stack to validate the parentheses. It features a dictionary to map closing to opening brackets, managing imbalance as it traverses the input.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 2: Two Pointer Approach (with a stack-like behavior)
This approach uses two pointers with stack-like behavior internally, taking advantage of simple list operations for push and pop.
def isValid(s: str) -> bool:
if len(s) % 2 != 0:
return False
stack =[]
for char in s:
if char in ['(', '{', '[']:
stack.append(char)
else:
if len(stack) == 0:
return False
top = stack.pop()
if not ((char == ')' and top == '(') or
(char == '}' and top == '{') or
(char == ']' and top == '[')):
return False
return len(stack) == 0public class Solution {
public boolean isValid(String s) {
if (s.length() % 2 != 0) return false;
StringBuilder stack = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.append(c);
} else {
int length = stack.length();
if (length == 0) return false;
char top = stack.charAt(length - 1);
stack.deleteCharAt(length - 1);
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '['))
return false;
}
}
return stack.length() == 0;
}
}#include <string>
bool isValid(std::string s) {
if (s.size() % 2 != 0) return false;
std::string stack;
for (char& c : s) {
if (c == '(' || c == '{' || c == '[') {
stack.push_back(c);
} else {
if (stack.empty()) return false;
char top = stack.back();
stack.pop_back();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '['))
return false;
}
}
return stack.empty();
}function isValid(s) {
if (s.length % 2 !== 0) return false;
const stack = [];
for (let char of s) {
if (char === '(' || char === '{' || char === '[') {
stack.push(char);
} else {
if (stack.length === 0) return false;
const top = stack.pop();
if (!((char === ')' && top === '(') ||
(char === '}' && top === '{') ||
(char === ']' && top === '['))) {
return false;
}
}
}
return stack.length === 0;
}
console.log(isValid("()[]{}")); // Output: true
console.log(isValid("(]")); // Output: false#include <stdbool.h>
#include <stdio.h>
#include <string.h>
bool isValid(char * s) {
int len = strlen(s);
if (len % 2 != 0) return false;
char stack[len / 2];
int top = -1;
for (int i = 0; s[i]; i++) {
switch (s[i]) {
case '(': case '{': case '[':
if (top == len / 2 - 1) return false;
stack[++top] = s[i];
break;
case ')':
if (top == -1 || stack[top--] != '(') return false;
break;
case '}':
if (top == -1 || stack[top--] != '{') return false;
break;
case ']':
if (top == -1 || stack[top--] != '[') return false;
break;
}
}
return top == -1;
}using System;
using System.Collections.Generic;
public class Solution {
public bool IsValid(string s) {
if (s.Length % 2 != 0) return false;
var stack = new List<char>();
foreach (char c in s) {
if (c == '(' || c == '{' || c == '[') {
stack.Add(c);
} else {
if (stack.Count == 0) return false;
char top = stack[stack.Count - 1];
stack.RemoveAt(stack.Count - 1);
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 Python code employs both length parity and stack growth inside looping. It performs element-wise checks against frequent boundary conditions, using a single output for validity.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Stack
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.
const map = new Map([
['(', ')'],
['[', ']'],
['{', '}'],
]);
function isValid(s: string): boolean {
const stack = [];
for (const c of s) {
if (map.has(c)) {
stack.push(map.get(c));
} else if (stack.pop() !== c) {
return false;
}
}
return stack.length === 0;
}func isValid(s string) bool {
stk := []rune{}
for _, c := range s {
if c == '(' || c == '{' || c == '[' {
stk = append(stk, c)
} else if len(stk) == 0 || !match(stk[len(stk)-1], c) {
return false
} else {
stk = stk[:len(stk)-1]
}
}
return len(stk) == 0
}
func match(l, r rune) bool {
return (l == '(' && r == ')') || (l == '[' && r == ']') || (l == '{' && r == '}')
}use std::collections::HashMap;
impl Solution {
pub fn is_valid(s: String) -> bool {
let mut map = HashMap::new();
map.insert('(', ')');
map.insert('[', ']');
map.insert('{', '}');
let mut stack = vec![];
for c in s.chars() {
if map.contains_key(&c) {
stack.push(map[&c]);
} else if stack.pop().unwrap_or(' ') != c {
return false;
}
}
stack.len() == 0
}
}# @param {String} s
# @return {Boolean}
def is_valid(s)
stack = ''
s.split('').each do |c|
if ['{', '[', '('].include?(c)
stack += c
else
if c == '}' && stack[stack.length - 1] == '{'
stack = stack.length > 1 ? stack[0..stack.length - 2] : ""
elsif c == ']' && stack[stack.length - 1] == '['
stack = stack.length > 1 ? stack[0..stack.length - 2] : ""
elsif c == ')' && stack[stack.length - 1] == '('
stack = stack.length > 1 ? stack[0..stack.length - 2] : ""
else
return false
end
end
end
stack == ''
endclass Solution {
/**
* @param string $s
* @return boolean
*/
function isValid($s) {
$stack = [];
$brackets = [
')' => '(',
'}' => '{',
']' => '[',
];
for ($i = 0; $i < strlen($s); $i++) {
$char = $s[$i];
if (array_key_exists($char, $brackets)) {
if (empty($stack) || $stack[count($stack) - 1] !== $brackets[$char]) {
return false;
}
array_pop($stack);
} else {
array_push($stack, $char);
}
}
return empty($stack);
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n) |
| Two Pointer Approach (with a stack-like behavior) | Time Complexity: O(n) |
| Stack | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Valid Parentheses easy or hard?
Valid Parentheses is classified as an Easy problem on LeetCode, but it introduces an important concept used in many harder problems: stack-based validation of nested structures. It often serves as a foundational interview question before moving to more complex stack problems.
How to solve Valid Parentheses in O(n)?
Traverse the string once while maintaining a stack of opening brackets. When you encounter a closing bracket, compare it with the element on the top of the stack. If the types match, pop the stack; otherwise the string is invalid. If the stack is empty at the end, the parentheses are valid.
What is the best approach for Valid Parentheses?
The stack-based approach is the most reliable and widely used solution. Iterate through the string, push opening brackets onto a stack, and pop when matching closing brackets appear. This ensures the most recently opened bracket closes first. The algorithm runs in O(n) time with O(n) space.
What data structure is used in Valid Parentheses?
A stack is the primary data structure used to solve this problem. It keeps track of the order of opening brackets and ensures they close in reverse order. The LIFO property of stacks perfectly matches the nesting behavior of parentheses.
What is the time complexity of Valid Parentheses?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once during the scan. Stack push and pop operations are constant time, so the total work grows linearly with the input size.
Valid Parentheses Python or Java solution approach?
Both Python and Java solutions typically implement the same stack-based algorithm. Iterate through the string, push opening brackets, and validate closing brackets against the stack top. The implementation remains O(n) time and O(n) space regardless of language.
Is Valid Parentheses asked at Google, Amazon, or Meta?
Valid Parentheses frequently appears in interviews at companies like Amazon, Google, Meta, and Microsoft as an entry-level data structures question. It tests understanding of stack operations, string traversal, and edge case handling with nested structures.