# The Paired Doors

> Every open bracket has a partner - but not every partner shows up.

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

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given a string containing only '()', '[]', '{}', return True if all brackets are balanced and properly nested, else False.

## Worked solution and explanation

### Why this problem exists in real interviews

This is a classic **stack-based matching** problem. It tests whether candidates can use a stack to enforce correct nesting of paired symbols, a pattern used in parsers, compilers, and code validators.

---

### Break down the requirements

#### Step 1: Map closing brackets to their opening counterparts

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

#### Step 2: Push opening brackets onto the stack

When encountering `(`, `[`, or `{`, push it.

#### Step 3: On closing brackets, check the stack top

Pop the stack and verify it matches the expected opening bracket. If not, the string is invalid.

#### Step 4: Final check: stack must be empty

If the stack has leftover opening brackets after scanning, the string is invalid.

---

### The solution

**Stack-based bracket matching**

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

> **Time and Space Complexity**
>
> **Time:** O(n) with a single pass through the string.
> 
> **Space:** O(n) in the worst case when all characters are opening brackets.

> **Interviewers Watch For**
>
> Do you check `not stack` before accessing `stack[-1]`? An unmatched closing bracket on an empty stack causes an IndexError without this guard.

> **Common Pitfall**
>
> Only checking that the count of opening and closing brackets matches. This misses ordering violations like `([)]` which has equal counts but incorrect nesting.

---

## Common follow-up questions

- What if the string also contained non-bracket characters? _(Tests ignoring characters that are not brackets.)_
- How would you return the index of the first invalid bracket? _(Tests tracking position alongside the stack.)_
- What if you needed to find the minimum number of removals to make it valid? _(Tests a more complex stack-based counting algorithm.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_paired_doors)
- [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.