DSA With AI
Week 2 ยท Stack

Valid Parentheses

Decide whether every closing bracket matches the most recent unmatched opening bracket.

Easy Stack Week 2 Practice runner

Frame the problem

  • Bracket order matters.
  • Types must match.
  • An empty stack is required at the end.
1. Reveal example inputs and outputs

Example 1

Input:

is_valid_parentheses("()[]{}")

Output:

true

Example 2

Input:

is_valid_parentheses("(]")

Output:

false
2. Brute force first

Why are counts of each bracket type insufficient for nested strings like ([)]?

3. Reveal the insight ladder
  1. Push opening brackets.
  2. For a closing bracket, the stack top must be its matching opener.
  3. If the stack is empty or mismatched, return False.
  4. At the end, all openers must have been closed.
4. Dry run before code
  1. s = ({[]}).
  2. Push (, {, [.
  3. Then ], }, ) each match the stack top.
  4. The stack ends empty, so return True.
5. Reveal final Python solution 
def is_valid_parentheses(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif not stack or stack.pop() != pairs[char]:
            return False
    return not stack

Complexity: Time O(n), space O(n) in the worst case.

Interview narration

  • The most recent opener is the only one a closer can legally match.
  • That last-in-first-out rule is exactly a stack.
  • The final empty stack proves no unmatched openers remain.

Common traps

  • Using counts instead of order.
  • Not checking for an empty stack before popping.
  • Forgetting leftover openers at the end.

Follow-up drills

1. How would you include other characters?

Ignore non-bracket characters or reject them depending on the prompt. Make that policy explicit before coding.

2. How would you report the first error position?

Store opener indices on the stack and return the current closer index when a mismatch or empty-stack close occurs.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.