March 24
Valid Parentheses
How to notice that each closing bracket must match the most recent opening one and why that calls for a stack.
Stack Beginner 15 min TypeScript
Given a string s containing only the characters ()[]{}, return true if the string is valid.
A string is valid when:
- every opening bracket is closed by the same type
- every opening bracket is closed in the correct order
Example:
Input: s = "()[]{}"
Output: true
What to notice before coding
- Matching counts of openings and closings is not enough.
- The current closing bracket must match the most recent unresolved opening bracket.
- If a closing bracket appears when nothing is open, the answer is already `false`.
Common mistakes
- validating only the count of each symbol
- looking for any compatible opening instead of the most recent one
Step 1 — Understand what really needs to be validated
A lot of people start by looking only at counts.
But this problem is not about quantity. It is about order and context.
([)] proves that:
- opened
( - opened
[ - closed
)before closing[
The counts match. The structure does not.
Step 2 — Write a correct baseline
One possible baseline is to keep removing visible valid adjacent pairs until nothing changes:
export function isValid(s: string): boolean {
let current = s
let previous = ''
while (current.length !== previous.length) {
previous = current
current = current.replace('()', '').replace('[]', '').replace('{}', '')
}
return current.length === 0
}
It works, but it is inefficient. Each pass creates new strings and repeats work.
Step 3 — Reframe the question
When a closing bracket arrives, what do you actually need to know?
Not "does some opening bracket of this type exist?".
It is:
does the last unresolved opening bracket match this closing bracket?
That points straight to a LIFO structure.
Step 4 — Store the open context
A stack does exactly that:
- opening bracket: push
- closing bracket: pop
- wrong type: fail
- end of input: stack must be empty
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function isValid(s: string): boolean {
// your solution here
return false
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(n)
Solution 1 — Remove pairs O(n²)
A simple baseline is to keep removing visible valid pairs.
export function isValid(s: string): boolean {
let current = s
let previous = ''
while (current.length !== previous.length) {
previous = current
current = current.replace('()', '').replace('[]', '').replace('{}', '')
}
return current.length === 0
}It works. But it is expensive because the string is reprocessed again and again.
Solution 2 — Stack O(n)
If each closing bracket must match the most recent opening one, use a stack.
export function isValid(s: string): boolean {
const pairs: Record<string, string> = {
')': '(',
']': '[',
'}': '{',
}
const stack: string[] = []
for (const char of s) {
if (char in pairs) {
if (stack.pop() !== pairs[char]) {
return false
}
continue
}
stack.push(char)
}
return stack.length === 0
}Now the data structure matches the shape of the problem.
What to say in the interview
A strong short explanation would be:
This is not only a counting problem. Each closing bracket has to match the most recent opening bracket that is still unresolved. That is why a
stackfits well: push openings, pop on closing, and validate the type inO(n).
That shows that you:
- identified the real rule of the problem
- justified the data structure
- explained the solution in terms of context, not a memorized trick
When this pattern shows up again
The same pattern comes back when you need to:
- track open context
- validate closing order
- undo the last state first
- process nested structures
The point is not memorizing
stack.
The point is noticing when the problem says “last in, first out.”