Vibe Engines Learn
CODING CHALLENGE · N°02

Valid Parentheses

Easy StackStrings

The canonical stack problem: decide whether every bracket is closed by the right type, in the right order. A stack turns nested matching into a single pass. Solve it in Python or TypeScript.

The problem

Given a string s of just the characters ()[]{}, decide whether it is valid: every open bracket is closed by a bracket of the same type, and brackets close in the right order (the most recently opened closes first). Return a boolean.

EXAMPLE 1
Input s = "()"
Output true
EXAMPLE 2
Input s = "()[]{}"
Output true
EXAMPLE 3
Input s = "(]"
Output false
wrong type
EXAMPLE 4
Input s = "([)]"
Output false
wrong order
EXAMPLE 5
Input s = "{[]}"
Output true
properly nested
CONSTRAINTS
  • 1 ≤ s.length ≤ 10⁴
  • s contains only the six bracket characters.
  • A stack gives O(n) time and O(n) space.
SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement is_valid(s): return True only if the brackets are balanced and correctly nested. Push opens onto a stack; on a close, the top of the stack must be its matching open.

HINTS — 4 IDEAS
  1. The most recently opened bracket must be the first one closed — that is exactly a stack (last in, first out).
  2. Push every opening bracket. On a closing bracket, pop and check it matches.
  3. A map from closing → opening makes the match check one lookup.
  4. It is invalid if a close finds an empty stack (nothing to match) — and at the end the stack must be empty.
CPython · WebAssembly
Approach, complexity & discussion — open after you solve

The approach

Use a stack. Push every opening bracket; on a closing bracket, the top of the stack must be its matching opener — pop it if so, fail if not (or if the stack is empty). The string is valid only if the stack is empty at the end, which catches unclosed openers.

Complexity

Time O(n) — one pass; space O(n) for the stack in the worst case (all openers).

Common mistakes

  • Not checking the stack is empty at the end, so "(((" is wrongly accepted.
  • Popping an empty stack on a stray closing bracket — check emptiness first.
  • Only counting brackets rather than matching types and order, so "([)]" slips through — it must fail.

Where this shows up

This is the canonical stack problem, and the “match nested pairs with a stack” pattern is exactly how parsers, expression evaluators, JSON/XML validators, and your editor’s bracket-matching work. Recognizing that “most recent unmatched open” means “stack” is the transferable insight.

Explore the topic

See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.

Algorithms & DSA Interview Prep