# Open and Shut

> Every opener is a promise. The order you close them in decides whether it holds.

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

Domain: Python · Difficulty: easy · Seniority: L5

## Problem

A config parser has to reject malformed input before it reaches the evaluator. Given a string `s` that mixes the three bracket pairs `()`, `[]`, `{}` with arbitrary other characters, return whether every bracket is closed by the correct type and in the right nesting order. Treat any non-bracket character as filler, and treat an empty string as balanced.

## Worked solution and explanation

### What this really is

Strip the validator framing and this is a last-in-first-out matching problem: the most recently opened bracket must be the next one to close. Anyone can count brackets and confirm the totals line up. What actually separates candidates is catching the two strings where counting lies. In '([)]' the counts are perfect but the square bracket closes while a parenthesis is still open, so the nesting is wrong. In '({' nothing ever mismatches, yet two openers are left dangling at the end. Miss either and your validator waves malformed input straight through to the evaluator.

> **Trick to solving**
>
> Push every opening bracket onto a stack. When you hit a closer, the top of the stack must be its matching opener: pop and move on. Two failure conditions kill the string: the stack is empty when you need to pop (a closer with no opener), or the stack is non-empty after the last character (openers that never closed).

---

### Break down the requirements

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

Build a dict mapping each closer to its opener: `)` to `(`, `]` to `[`, `}` to `{`. One lookup replaces a chain of if/elif comparisons and makes the match check a single expression.

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

Walk the string once. An opener gets pushed. A closer must find a matching opener on top of the stack, else you can bail immediately. Anything that is neither is filler and gets skipped, which is what makes 'hello (world)' work without special-casing letters.

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

The loop alone is not enough. A string like '({' never triggers a mismatch because no closer ever arrives. The only way to catch leftover openers is to confirm the stack is empty once the loop ends.

---

### 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()
    return not stack
```

*One pass, O(n) time; the closing check covers both the wrong-type and the empty-stack cases.*

> **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, hit when the string is all openers.

> **Interviewers watch for**
>
> The dict lookup over an if/elif ladder, and the final emptiness check. Candidates who only validate inside the loop and return True at the bottom are the ones who silently accept '({'. That single line is the tell.

> **Common pitfall**
>
> Forgetting the `not stack` guard before reading `stack[-1]`. A closer that arrives with an empty stack has no opener to match and must return False right away, not blow up on an index error.

---

## Common follow-up questions

- What if you needed to return the position of the first mismatch instead of a boolean? _(Tests tracking the index alongside the stack operations.)_
- How would you handle quoted regions that disable bracket matching? _(Tests a state machine that toggles an 'inside quotes' flag so brackets inside a string literal are ignored.)_
- If the string contained only one type of bracket, what could you drop? _(Tests simplifying to a single counter instead of a stack.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/open_and_shut)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.