Log inSign up
easyleetcodeNot Started

Valid Parentheses

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets. 2. Open brackets must be closed in the correct order. 3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true
Explanation: The parentheses match correctly.

Example 2:

Input: s = "()[]{}"
Output: true
Explanation: All three pairs of brackets open and close in correct matching order.

Example 3:

Input: s = "(]"
Output: false
Explanation: ( is incorrectly closed by ].

Example 4:

Input: s = "([])"
Output: true
Explanation: Nested brackets open and close in correct inner-to-outer order.

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply LIFO stack to nested bracket validation.
  • Eliminate hash map lookups by pushing expected counterparts.
  • Handle empty stack underflow and trailing unclosed bracket edge cases.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Matching opening and closing delimiters in nested hierarchical structures.
  • Syntax validation and compiler parsing.

Algorithmic Decision Tree:

  • Matching opening and closing delimiters in nested hierarchical structures.
  • Syntax validation and compiler parsing.

Connected Patterns:

Generate ParenthesesMinimum Remove to Make Valid ParenthesesLongest Valid Parentheses

1. Iterative String Pair Replacement

Intuition

While string contains "()", "{}", or "[]", replace all occurrences with the empty string "". If the resulting string is empty, return true; else false.

When to apply: Basic baseline conceptual solution.

Algorithm

  1. While s.includes('()') || s.includes('{}') || s.includes('[]'):
  2. Replace "()" with "".
  3. Replace "{}" with "".
  4. Replace "[]" with "".
  5. Return s.empty().

Iterative Adjacent Pair Replacement Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(), [], {}]
Current operationSTEP 1 OF 6
Observation: A string of brackets is valid if adjacent matched pairs can be iteratively canceled out
Visual state
Values and pointers at this exact step
array
S
()
[]
{}
0
1
2
Variables at this step
s
()[]{}
Length
6
Check / comparison
String contains "()", "[]", or "{}".
Decision / next transition
Loop while s.includes("()") || s.includes("[]") || s.includes("{}").
Why this step matters

Observation: A string of brackets is valid if adjacent matched pairs can be iteratively canceled out.

Decision: Repeatedly replace "()", "[]", "{}" with "" until no pairs remain.

Invariant: Length decreases by 2 on each replacement.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 bool isValid(std::string s) {
7 if (s.size() % 2 != 0) return false;
8 size_t pos;
9 while ((pos = s.find("()")) != std::string::npos ||
10 (pos = s.find("{}")) != std::string::npos ||
11 (pos = s.find("[]")) != std::string::npos) {
12 s.erase(pos, 2);
13 }
14 return s.empty();
15 }
16};
17
18int main() {
19 Solution sol;
20 std::cout << (sol.isValid("()[]{}") ? "true" : "false") << std::endl; // true
21 std::cout << (sol.isValid("(]") ? "true" : "false") << std::endl; // false
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(N^2) — Up to N / 2 replacements, each taking O(N) string scanning and copying.
  • Space complexity: O(N)

Why Brute Force Doesn't Scale:

Pushing expected closing character eliminates hash map / switch lookup on pop.

Preallocated dynamic array stack.

2. Stack with Hash Map Matching

Intuition

Define map = {')': '(', '}': '{', ']': '['}. For each character c in s: if c is a closing bracket, check if stack is non-empty and stack.pop() == map[c]. If c is an opening bracket, push onto stack. Return stack.empty().

When to apply: Standard canonical stack implementation.

Algorithm

  1. If s.length % 2 != 0: return false.
  2. Initialize stack and bracket map.
  3. For c in s:
  4. If c is in map (closing bracket):
  5. If stack empty or stack.pop() != map[c]: return false.
  6. Else: stack.push(c).
  7. Return stack.empty().

Stack with Hash Map Matching Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(, ), [, ], {, }]
Current operationSTEP 1 OF 6
Observation: First character is '('
Visual state
Values and pointers at this exact step
array
S
(
)
[
]
{
}
0
1
2
3
4
5
Variables at this step
Stack
["("]
Top
(
Check / comparison
Process s[0]='('. Opening bracket -> push to stack. Stack: ['('].
Decision / next transition
Push opening bracket to LIFO stack.
Why this step matters

Observation: First character is '('.

Decision: Since it is an opening bracket, push to stack.

Invariant: Stack holds unclosed opening brackets in arrival order.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <stack>
4#include <unordered_map>
5
6class Solution {
7public:
8 bool isValid(std::string s) {
9 if (s.size() % 2 != 0) return false;
10 std::unordered_map<char, char> map = {{')', '('}, {'}', '{'}, {']', '['}};
11 std::stack<char> st;
12
13 for (char c : s) {
14 if (map.count(c)) {
15 if (st.empty() || st.top() != map[c]) return false;
16 st.pop();
17 } else {
18 st.push(c);
19 }
20 }
21 return st.empty();
22 }
23};
24
25int main() {
26 Solution sol;
27 std::cout << (sol.isValid("()[]{}") ? "true" : "false") << std::endl; // true
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass over characters, each pushed and popped at most once.
  • Space complexity: O(N)

3. Push Expected Closing Characters onto Stack (Optimal)

Intuition

When reading '(', push ')'. When reading '{', push '}'. When reading '[', push ']'. If reading a closing bracket, verify !stack.empty() && stack.pop() == c. At the end of the string, return stack.empty().

When to apply: The standard fastest implementation with minimal branch misprediction and no map allocation.

Algorithm

  1. If s.length % 2 != 0: return false.
  2. Initialize stack.
  3. For c in s:
  4. If c == '(': stack.push(')').
  5. Else if c == '{': stack.push('}').
  6. Else if c == '[': stack.push(']').
  7. Else if stack.empty() || stack.pop() != c: return false.
  8. Return stack.empty().

LIFO Bracket Stack Matching with Invariant Validation

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [(, [, {, }, ], )]
Current operationSTEP 1 OF 7
Observation: Read s[0] = '('
Visual state
Values and pointers at this exact step
array
S
(
[
{
}
]
)
0
↑ i=0: '('
1
2
3
4
5
Variables at this step
Current Char
(
Action
Push
Stack
['(']
Check / comparison
Read s[0]='('. Opening bracket.
Decision / next transition
Push '(' onto stack. Stack is ['('].
Why this step matters

Observation: Read s[0] = '('. It is an opening delimiter.

Decision: Push '(' onto the LIFO stack.

Invariant: Stack contains unmatched opening brackets in strict order of arrival.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <stack>
4
5class Solution {
6public:
7 bool isValid(std::string s) {
8 if (s.size() % 2 != 0) return false;
9 std::stack<char> st;
10 for (char c : s) {
11 if (c == '(') st.push(')');
12 else if (c == '{') st.push('}');
13 else if (c == '[') st.push(']');
14 else {
15 if (st.empty() || st.top() != c) return false;
16 st.pop();
17 }
18 }
19 return st.empty();
20 }
21};
22
23int main() {
24 Solution sol;
25 std::cout << (sol.isValid("()") ? "true" : "false") << std::endl; // true
26 std::cout << (sol.isValid("()[]{}") ? "true" : "false") << std::endl; // true
27 std::cout << (sol.isValid("(]") ? "true" : "false") << std::endl; // false
28 std::cout << (sol.isValid("([)]") ? "true" : "false") << std::endl; // false
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N) strictly — Single linear pass with direct character comparisons.
  • Space complexity: O(N) stack memory

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Repeated String ReplacementO(N^2)O(N)Simple while loop replacing (), {}, [] with empty strings.Quadratic string copying overhead, unacceptable on large inputs.
2.LIFO Stack with Matching TableO(N)O(N)Standard clear hash map lookup with stack.Hash map lookup overhead on each character.
3.LIFO Stack Pushing Expected Closing Brackets (Optimal)OptimalO(N)O(N)Zero map lookup overhead, fastest direct branch execution, single pass.None.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Returning true before checking stack.empty() (e.g. '(' leaves stack non-empty).

Pitfall 2:

Not guarding against stack underflow before calling .pop() / .top().

Crucial Edge Cases to Validate:

  • Odd length string (s = (()): Early exit s.length % 2 != 0 returns false in O(1).
  • Closing bracket first (s = ]()): stack is empty on first character, returns false immediately.
  • Unclosed opening brackets (s = (((): Loop ends with stack containing 3 items; stack.empty() returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the odd-length parity optimization s.length % 2 != 0 right away.
  2. Explain the expected-bracket push pattern as a clean, idiomatic pattern.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does pushing the expected closing bracket instead of the opening bracket improve performance and clarity?

Back to DSA Sheet