~/workshop
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
falsewrong type
EXAMPLE 4
Input
s = "([)]"Output
falsewrong order
EXAMPLE 5
Input
s = "{[]}"Output
trueproperly nested
CONSTRAINTS
- 1 ≤ s.length ≤ 10⁴
- s contains only the six bracket characters.
- A stack gives O(n) time and O(n) space.
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
- The most recently opened bracket must be the first one closed — that is exactly a stack (last in, first out).
- Push every opening bracket. On a closing bracket, pop and check it matches.
- A map from closing → opening makes the match check one lookup.
- It is invalid if a close finds an empty stack (nothing to match) — and at the end the stack must be empty.
1
1