Given a string s containing only the bracket characters '(', ')', '{', '}', '[' and ']', decide whether it is valid.
A string is valid when:
- every opening bracket is closed by a matching bracket of the same type, and - brackets close in the correct order (the most recently opened bracket must be the first to close).
Return true if s is valid and false otherwise. The empty string is valid.
Example
One opening bracket closed by its match.
Constraints
- 1 <= s.length <= 10^4
- s consists only of the characters '()[]{}'.
Intuition
The brittle first idea is to strip matched pairs repeatedly: scan for an adjacent (), [], or {}, delete it, and start over, until the string stops shrinking. If you end at the empty string it was balanced. It works, but each deletion rescans the whole string.
function isValid(s) {
let prev;
// Keep deleting innermost pairs until the string stops changing.
do {
prev = s;
s = s.replace('()', '').replace('[]', '').replace('{}', '');
} while (s !== prev);
// Balanced iff everything cancelled away.
return s.length === 0;
}Each replace rescans the string and we may loop O(n) times, so this is O(n²) — and the string copying makes it worse. Can we do better?
The key observation: a closer must always match the most recently opened still-unclosed bracket. “Most recent, handled first” is the definition of a stack. Push every opener; on a closer, the top of the stack must be its matching opener — pop it. A mismatch, or a closer with an empty stack, is an immediate false. After one pass the stack must be empty (no dangling openers).
One left-to-right scan, O(1) work per character. Walking it through on a string that nests then breaks:
s = "([)]" — a wrong-order mismatch
An opener: remember it. Stack (bottom→top): [ ( ].
Another opener nests inside. Stack: [ (, [ ].
The closer ')' wants '(' on top, but the most-recent opener is '[' — the nesting order is broken.
We never reach index 3. The single mismatch is enough to reject the whole string.
- A contrasting valid string like
"{[]}"would push{, push[, then meet](top[✓, pop), then}(top{✓, pop), ending with an empty stack — balanced.
Optimization
Stack
Scan left to right. Push every opening bracket onto a stack. On a closing bracket, the top of the stack must be its matching opener — if the stack is empty or the top doesn't match, the string is invalid. After the scan the stack must be empty (no unclosed openers).
A map from each closer to its expected opener keeps the matching check O(1).
O(n) time, O(n) space.
/**
* @param {string} s
* @return {boolean}
*/
function isValid(s) {
const pairs = { ")": "(", "]": "[", "}": "{" };
const stack = [];
for (const ch of s) {
if (ch === "(" || ch === "[" || ch === "{") {
stack.push(ch);
} else if (stack.pop() !== pairs[ch]) {
return false;
}
}
return stack.length === 0;
}Complexity analysis
Time complexity: O(n). Here's why:
- Each character is visited exactly once in a single left-to-right scan.
- A push, a pop, and a map lookup are all O(1).
So the work is n × O(1) = O(n), where n is the string length — a clean linear pass, versus the brute force's repeated O(n²) deletions.
Space complexity: O(n). Here's why:
- The stack holds the unclosed openers seen so far.
- A fully nested string like
"((((("puts every character on the stack at once.
So the stack can grow to n entries in the worst case — overall O(n) auxiliary space.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| s = "()" | true | A single matched pair. |
| s = "" | true | The empty string is vacuously balanced. |
| s = ")" | false | A lone closer — the stack is empty, nothing to match. |
| s = "(()" | false | An opener left unclosed — the stack isn't empty at the end. |
| s = "[](){}" | true | Three independent matched pairs in a row. |
| s = "([)]" | false | Interleaved, not nested — wrong close order. |
Try it yourself
Write your solution against the real judge before checking the reference.