How do you solve Valid Parentheses?

Iterate through the string once, pushing opening brackets onto a stack. For each closing bracket, check if the stack is non-empty and the top matches the corresponding opening bracket. If so, pop the stack; otherwise, return false immediately. After processing all characters, if the stack is empty, return true; else, return false.

What pattern does Valid Parentheses use?

The Pattern: Stacks (Bracket Matching) The Heuristic: Use a stack to track the most recent unmatched opening bracket; a closing bracket must match the stack's top to maintain validity, enabling O(n) validation by simulating the nesting structure.

Valid Parentheses — Stacks

Q: What is the time complexity of Valid Parentheses?

O(n). Each character is processed once. Stack push and pop operations are O(1), so total time is linear in the length of the string.

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid by checking if every opening bracket has a corresponding closing bracket in the correct order.

1 ≤ s.length ≤ 10⁴
s consists only of '()[]{}'.

Example

Input: s = "()[]{}"

Output: true

The algorithm uses a stack to track opening brackets. It iterates through each character: when it encounters an opening bracket, it pushes it onto the stack. When it encounters a closing bracket, it checks if the top of the stack matches the corresponding opening bracket. For the input "()[]{}", the stack operations proceed as follows: - '(' is pushed. - ')' matches the top '(' and pops it. - '[' is pushed. - ']' matches the top '[' and pops it. - '{' is pushed. - '}' matches the top '{' and pops it. At the end, the stack is empty, indicating all brackets were matched correctly, so the function returns true.

Approach

Straightforward Solution

A brute-force approach might try to repeatedly find matching pairs and remove them from the string, which is inefficient (O(n²)) due to repeated scanning and string manipulation.

Core Observation

Valid parentheses require that every closing bracket matches the most recent unmatched opening bracket of the same type, which naturally suggests a Last-In-First-Out (LIFO) data structure.

Path to Optimal

Preview

The key insight is to use a stack to track opening brackets as they appear. When a closing bracket is encountered, the algorithm checks if it matches the top of the stack…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through the string once, pushing opening brackets onto a stack. For each closing bracket, check if the stack is non-empty and the top matches the corresponding opening bracket…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each character is processed once. Stack push and pop operations are O(1), so total time is linear in the length of the string.

Space

O(n)

In the worst case, all characters are opening brackets, requiring storage of all in the stack. This auxiliary space scales linearly with input size.

Solution

Python

1class Solution:
  def isValid(self, s: str) -> bool:
      stack = []
      close_to_open = {")": "(", "]": "[", "}": "{"}
5
      for char in s:
          if char in close_to_open:
              if stack and stack[-1] == close_to_open[char]:
                  stack.pop()
              else:
                  return False
          else:
              stack.append(char)
      
      return not stack

Step-by-Step Solution

1

Initialize Stack and Bracket Mapping for Validation

3stack = []
4close_to_open = {")": "(", "]": "[", "}": "{"}

Objective

To prepare the data structures needed for efficient bracket matching during iteration.

Key Insight

A stack naturally models the nested structure of brackets by tracking unmatched opening brackets. A dictionary mapping closing brackets to their corresponding opening brackets enables constant-time matching checks, simplifying the validation logic.

Interview Quick-Check

Core Logic

The stack stores unmatched opening brackets, and the dictionary provides O(1) lookup to verify if a closing bracket matches the expected opening bracket.

Common Pitfalls & Bugs

Forgetting to initialize the mapping or using incorrect pairs leads to wrong matching logic and incorrect results.

2

Iterate Through Characters and Validate Bracket Pairs

To process each character, pushing opening brackets and validating closing brackets against the stack's top.

3

Confirm Complete Matching by Checking Stack Emptiness

To determine if all opening brackets have been matched by verifying the stack is empty after processing the entire string.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 15 Critical

return not stack

Return true if the stack is empty, indicating all brackets matched correctly.

An empty stack confirms that every opening bracket found a matching closing bracket in the correct order, validating the string's correctness.

Line 8 Critical

if stack and stack[-1] == close_to_open[char]:

Verify the stack is not empty and the top matches the expected opening bracket.

This condition ensures that the closing bracket correctly matches the most recent unmatched opening bracket, preserving the nesting order.

Line 10 Critical

else:

Handle the case where the closing bracket does not match the stack's top.

An immediate return of false prevents further processing of an invalid string, optimizing performance and correctness.

Full line-by-line criticality + rationale for all 11 lines available on Pro.

Test Your Understanding

Why does the algorithm return false immediately when a closing bracket does not match the top of the stack?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Valid Parentheses from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Valid Parentheses drill

or drill a free problem

1	`class Solution:`
2	`def isValid(self, s: str) -> bool:`
3	`stack = []`
4	`close_to_open = {")": "(", "]": "[", "}": "{"}`
5
6	`for char in s:`
7	`if char in close_to_open:`
8	`if stack and stack[-1] == close_to_open[char]:`
9	`stack.pop()`
10	`else:`
11	`return False`
12	`else:`
13	`stack.append(char)`
14
15	`return not stack`