Problem overview
The method isValid receives a string input that contains only the characters (, ), {, }, [ and ]. It returns true when the brackets are balanced and false otherwise. Two rules define "balanced": every opening bracket is closed by a bracket of the same type, and brackets are closed in the correct order, so that the one opened last is the one closed first.
Some examples: "()", "()[]{}" and "{[]}" are valid. "(]" is invalid because the types differ. "([)]" is invalid even though each bracket has a partner of the right type: the ) arrives while the [ opened after the ( is still open, so the order is wrong. The statement asks for O(n) time and O(n) extra space.
Approach: a stack of unmatched opening brackets
Whenever a closing bracket appears, it must close the most recent opening bracket that is still open. "Most recent first" is the behaviour of a stack (last in, first out), so a stack is the natural tool.
Scan the string from left to right:
- An opening bracket cannot be checked yet, so push it on the stack.
- A closing bracket must match the bracket on top of the stack. Pop the top and compare. If the stack is empty, or the popped bracket is of the wrong type, the string is invalid.
When the scan ends, the stack must be empty. If anything is left, some opening bracket was never closed.
Here is "([)]": push (, push [. Then ) arrives and the top is [, which belongs to ], not to ), so the answer is false right away. With "{[]}": push {, push [, then ] pops [ (a match), then } pops { (a match), and the stack ends empty, so the answer is true.
A cheaper idea that counts each kind of bracket fails on "([)]", because the counts balance while the order is wrong. Repeatedly deleting adjacent pairs such as () from the string works, but each deletion copies the string, so it is quadratic. The stack visits each character once.
Step by step
- Map each opener to its closer. A
Map<Character, Character>namedclosingBracketsholds'('to')','{'to'}'and'['to']'. The lesson fills it with a double-brace initializer. - Create the stack. A
Stack<Character>namedstackholds the openers that wait for a partner. - Loop over the characters with an enhanced
foroverinput.toCharArray(), using acharvariable calledbracket. - Detect an opener. A character is an opening bracket exactly when it is a key of
closingBrackets, socontainsKeyis the test. - Push the opener onto the stack.
- Handle everything else in the
elsebranch. Since the input only has brackets, a character that is not an opener is a closer. - Reject a closer with nothing open. If the stack is empty, return
false. This check must come before the pop, because popping an emptyStackthrows. - Pop the most recent opener into a
charnamedopenBracket. - Compare. Look up what
openBracketshould be closed by, withclosingBrackets.get(openBracket). If the currentbracketdiffers, returnfalse. - Check for leftovers. After the loop, return whether the stack is empty. A non-empty stack means some opener was never closed.
The solution in Java
class Solution {
public boolean isValid(String input) {
Map<Character, Character> closingBrackets = new HashMap<>() {{
put('(', ')');
put('{', '}');
put('[', ']');
}};
Stack<Character> stack = new Stack<>();
for (char bracket : input.toCharArray()) {
if (closingBrackets.containsKey(bracket)) {
stack.push(bracket);
} else {
if (stack.size() == 0) {
return false;
}
char openBracket = stack.pop();
if (bracket != closingBrackets.get(openBracket)) {
return false;
}
}
}
return stack.size() == 0;
}
}
The Java details worth knowing:
- Imports.
Map,HashMapandStackare injava.util, so a file of your own needsimport java.util.*;. - The double-brace initializer.
new HashMap<>() {{ ... }}creates an anonymous subclass ofHashMapwhose initializer block callsput. It is compact but creates an extra class, and the object's class is no longer exactlyHashMap. For a small fixed map,Map.of('(', ')', '{', '}', '[', ']')is the modern alternative. - Autoboxing. The map and the stack hold
Characterobjects, whilebracketis a primitivechar. Java boxes it oncontainsKeyandpush, and unboxes the popped value intochar openBracket. Inbracket != closingBrackets.get(openBracket), the right side is aCharacter, which is unboxed because the left side is a primitive, so the comparison is between characters, not references. - Popping an empty stack throws.
Stack.pop()on an empty stack throwsEmptyStackException. That is why the size check comes first, and why an input such as")"returnsfalseinstead of crashing. StackversusArrayDeque.Stackis a legacy class whose methods are synchronized. New code usually usesDeque<Character> stack = new ArrayDeque<>()withpush,popandisEmpty(). The logic stays identical.
Complexity
Time: O(n), where n is the length of the string. Each character is handled once, and each push, pop and map lookup takes constant time on average.
Space: O(n). In the worst case, such as "(((((", every character is an opener and the stack holds them all. The map has three entries whatever the input.
Edge cases and common mistakes
- Only closing brackets.
")"or"]["reach a closer with an empty stack and returnfalse. - Only opening brackets.
"(("never fails inside the loop, and the final emptiness check is what returnsfalse. Forgetting that last check is the most frequent bug:return trueat the end would accept"(". - Odd length. A valid string has an even number of characters, because brackets come in pairs. An early
input.length() % 2 == 1check is a cheap shortcut but not required. - Right counts, wrong order.
"([)]"and")("show why counting is not enough. - Checking only the type, not the top. Comparing against any open bracket instead of the one on top accepts
"([)]". - Empty string. The constraints guarantee at least one character, but an empty string would return
true: nothing is open and nothing is unmatched.
Testing
"()"givestrue."()[]{}"givestrue."{[()]}"givestrue."(]"givesfalse."([)]"givesfalse."(()"givesfalse, from the leftover opener."())"givesfalse, from the closer with an empty stack.
