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 - LeetCode Solution

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

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. If it does, the top is popped; if not, the string is invalid. This approach ensures a single pass through the string with O(n) time complexity.

Optimal Approach

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.

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

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

1class Solution {
  public boolean isValid(String s) {
      Deque<Character> stack = new ArrayDeque<>();
      Map<Character, Character> closeToOpen = new HashMap<>();
      closeToOpen.put(')', '(');
      closeToOpen.put(']', '[');
      closeToOpen.put('}', '{');
8
      for (char ch : s.toCharArray()) {
          if (closeToOpen.containsKey(ch)) {
              if (!stack.isEmpty() && stack.peek() == closeToOpen.get(ch)) {
                  stack.pop();
              } else {
                  return false;
              }
          } else {
              stack.push(ch);
          }
      }
20
      return stack.isEmpty();
  }
23}

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

6for 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)

Objective

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

Key Insight

By checking if a character is a closing bracket, the algorithm decides whether to validate against the stack or push a new opening bracket. Immediate return on mismatch prevents unnecessary processing and ensures correctness. This single-pass approach efficiently enforces the correct nesting order.

Interview Quick-Check

Core Logic

For each closing bracket, verify the stack is not empty and the top matches the expected opening bracket; if so, pop it, else return false immediately.

State & Boundaries

If the stack is empty when a closing bracket is encountered, the string is invalid because there is no matching opening bracket.

Common Pitfalls & Bugs

Not checking if the stack is empty before accessing its top can cause runtime errors.

3

Confirm Complete Matching by Checking Stack Emptiness

15	`return not stack`

Objective

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

Key Insight

An empty stack at the end means every opening bracket found a matching closing bracket in the correct order. Any remaining elements indicate unmatched brackets, invalidating the string.

Interview Quick-Check

Core Logic

Return true only if the stack is empty, confirming all brackets were matched correctly.

Common Pitfalls & Bugs

Failing to check stack emptiness at the end can lead to false positives when extra unmatched opening brackets remain.

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.

Line 11 Critical

return False

Return false when the closing bracket does not have a matching opening bracket on the stack.

This early exit is critical to avoid false positives and to signal that the string is invalid as soon as a mismatch is detected.

Line 3 Core

stack = []

Initialize an empty stack to track opening brackets.

The stack models the nested structure of brackets, enabling last-in-first-out matching essential for validating correct bracket order.

Line 4 Core

close_to_open = {")": "(", "]": "[", "}": "{"}

Create a dictionary mapping closing brackets to their corresponding opening brackets.

This mapping allows constant-time verification of matching pairs, simplifying the logic when encountering closing brackets.

Line 12 Core

else:

Handle characters that are opening brackets by pushing them onto the stack.

Storing opening brackets preserves the order for future matching with closing brackets, enabling the LIFO validation mechanism.

Line 13 Core

stack.append(char)

Push the current opening bracket onto the stack.

This action updates the stack state to reflect the presence of a new unmatched opening bracket, maintaining the correct nesting structure.

Line 7 Core

if char in close_to_open:

Check if the current character is a closing bracket.

Identifying closing brackets triggers the validation step against the stack's top, which is the core decision point in the algorithm.

Line 9 Core

stack.pop()

Pop the matching opening bracket from the stack.

Removing the matched opening bracket updates the stack state, reflecting that this pair has been successfully validated.

Line 6 Standard

for char in s:

Iterate over each character in the input string.

Processing characters sequentially ensures the algorithm respects the order of brackets, which is critical for correct nesting validation.

Test Your Understanding

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

Because a closing bracket must correspond to the most recent unmatched opening bracket to maintain correct nesting order; a mismatch indicates invalid parentheses structure that cannot be corrected later.

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`

1	`class Solution {`
2	`public boolean isValid(String s) {`
3	`Deque<Character> stack = new ArrayDeque<>();`
4	`Map<Character, Character> closeToOpen = new HashMap<>();`
5	`closeToOpen.put(')', '(');`
6	`closeToOpen.put(']', '[');`
7	`closeToOpen.put('}', '{');`
8
9	`for (char ch : s.toCharArray()) {`
10	`if (closeToOpen.containsKey(ch)) {`
11	`if (!stack.isEmpty() && stack.peek() == closeToOpen.get(ch)) {`
12	`stack.pop();`
13	`} else {`
14	`return false;`
15	`}`
16	`} else {`
17	`stack.push(ch);`
18	`}`
19	`}`
20
21	`return stack.isEmpty();`
22	`}`
23	`}`

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)`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Stack and Bracket Mapping for Validation

Iterate Through Characters and Validate Bracket Pairs

Confirm Complete Matching by Checking Stack Emptiness

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.