# The Bracket Validator

> Brackets opened and closed. The nesting might be off.

Canonical URL: <https://datadriven.io/problems/the_bracket_validator>

Domain: Python · Difficulty: easy · Seniority: L5

## Problem

Given a string, return True if all bracket pairs '()', '[]', '{}' are balanced and correctly nested. Other characters are ignored.

## Worked solution and explanation

### Why this problem exists in real interviews

Validating balanced brackets is the canonical **stack** problem. It tests whether you match openers with closers in LIFO order, a pattern that appears in parsers, compilers, and config validators.

> **Trick to Solving**
>
> Push every opening bracket onto a stack. When you encounter a closing bracket, pop the stack and verify it matches. If the stack is empty when you need to pop, or non-empty after processing all characters, the brackets are unbalanced.

---

### Break down the requirements

#### Step 1: Map closing brackets to their openers

Create a mapping: `)` to `(`, `]` to `[`, `}` to `{`.

#### Step 2: Push openers, pop and match closers

For each character, if it is an opener, push it. If it is a closer, pop and check the match.

#### Step 3: Verify the stack is empty at the end

Unmatched openers remain on the stack, indicating imbalance.

---

### The solution

**Stack-based bracket matching with pair validation**

```python
def is_balanced(s):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in matching:
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
    result = len(stack) == 0
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the string length. Each character is processed once.
> 
> **Space:** O(n) worst case for the stack (all openers).

> **Interviewers Watch For**
>
> Using a dict for the matching lookup and checking the stack is empty at the end. Both are essential correctness details.

> **Common Pitfall**
>
> Forgetting to check `not stack` before popping. A closing bracket with no corresponding opener should immediately return False.

---

## Common follow-up questions

- What if you needed to return the position of the first mismatch? _(Tests tracking the index alongside the stack operations.)_
- How would you handle nested quotes that disable bracket matching? _(Tests a state machine that toggles a 'inside quotes' flag.)_
- What if the string contains only one type of bracket? _(Tests simplifying to a counter instead of a stack.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_bracket_validator)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.