EasyDecide whether every bracket is correctly opened and closed.
Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', determine if the input is valid. Brackets must be closed by the same type and in the correct order, so every closing bracket matches the most recently opened one.
Walkthrough
only ()[]{} · max 30
try:
1
function isValid(s) {
2
const stack = [];
◄
3
const pairs = { ')':'(', ']':'[', '}':'{' };
4
for (const ch of s) {
5
if (ch in pairs) {
6
if (stack.pop() !== pairs[ch]) return false;
7
} else {
8
stack.push(ch);
9
}
10
}
11
return stack.length === 0;
12
}
no locals yet
string
(
[
{
}
]
)
stack
(empty)
STEP 0 / 13 · line 2
Start
Use a stack. Push every opening bracket; match each closing bracket against the top.
Intuition
The most recently opened bracket must be the first one closed — that “last in, first out” rule is exactly a stack.
Push every opening bracket. When a closing bracket arrives, the top of the stack must be its matching opener.
If the top does not match (or the stack is empty), the string is invalid.
After scanning everything, a valid string leaves the stack empty — nothing was left unclosed.
The algorithm
01Create an empty stack and a map from each closing bracket to its opener.
02For each character: if it is a closing bracket, pop the stack and check it equals the expected opener — otherwise return false.
03If it is an opening bracket, push it.
04At the end, return true only if the stack is empty.
Reference implementation
1
function isValid(s) {
2
const stack = [];
3
const pairs = { ')': '(', ']': '[', '}': '{' };
4
for (const ch of s) {
5
if (ch in pairs) {
6
if (stack.pop() !== pairs[ch]) return false;
7
} else {
8
stack.push(ch);
9
}
10
}
11
return stack.length === 0;
12
}
Complexity
Time
O(n) — each character is pushed/popped at most once.
Space
O(n) for the stack in the worst case (all opening brackets).