DSA-041 · FOCUSED PRACTICE
Valid Parentheses
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 55994 deterministic checks. Learner drafts are not executed.
Understand the problem
Determine whether a string of round, square, and curly brackets is properly nested and completely matched.
- s is non-null with 0–100,000 characters. Only (, ), [, ], {, } are allowed. Both methods validate the complete alphabet first and throw IllegalArgumentException for any other character, including spaces.
- Return true exactly when every closing bracket matches the most recent unmatched opening of its own type and no opening remains. Empty input is valid. A valid-alphabet structural mismatch returns false, not an exception.
- Preserve the immutable string. Nesting and bracket type matter; equal total opening/closing counts alone do not establish validity.
Examples
Input:
"([{}])"
Output:trueThe innermost curly pair closes before square and round pairs.
Input:
"([)]"
Output:falseThe round closer cannot close the currently unmatched square opening.
Before you start
- Stack top versus bottom and last-in-first-out order
- Loop invariants, checked arithmetic, and amortized analysis
Recognize the structure
The next closer has exactly one legal partner: the latest unmatched opening. A stack records this nesting order; a count only records how many opens remain and loses type and order.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 124/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Which unmatched opening must the next closer match?
Hint 2
What information does a count lose when bracket types differ?
Hint 3
Push openings, match the top on each closer, and require emptiness at completion.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Repeatedly erase adjacent matched pairs
Remove occurrences of (), [], and {} until a pass changes nothing. For ([{}]), remove {} to get ([]), then [] to get (), then () to get empty. For ([)], no adjacent pair can be erased, so it remains invalid. Every proper nonempty bracket sequence has an innermost adjacent pair; this gives a simple O(n²) worst-case baseline.
Improve the baseline
Record unmatched openings
Push each opening bracket onto an initially empty stack. The top is the only opening the next closer can legally complete.
Check before popping
For a closer, reject if the stack is empty or its top has a different type. Otherwise consume exactly that opening.
Check the leftover suffix obligation
After scanning, a nonempty stack means openings still await closers. Return true only when the stack is empty.
Why it is correct
Prefix invariant
Before each symbol, the stack from bottom to top is exactly the unmatched openings of the processed prefix, in nesting order. Pushing an opening extends that list.
Sound rejection and matching
An empty-stack closer has no available partner. A different top type cannot be bypassed without crossing pairs. A matching top closes the innermost pending pair and preserves the invariant.
Completion and termination
Every symbol is processed once after validation. If the scan succeeds, all encountered closers matched legally; emptiness proves no opening remains. Conversely every properly nested string follows these exact push/pop choices, so no valid string is rejected.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.ArrayDeque;
public final class Solution {
private static void validate(String s) {
for (int i = 0; i < s.length(); i++) if ("()[]{}".indexOf(s.charAt(i)) < 0) throw new IllegalArgumentException("brackets only");
}
public static boolean isValid(String s) {
validate(s);
ArrayDeque<Character> openings = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char symbol = s.charAt(i);
if (symbol == '(' || symbol == '[' || symbol == '{') openings.push(symbol);
else {
char expected = symbol == ')' ? '(' : symbol == ']' ? '[' : '{';
if (openings.isEmpty() || openings.pop() != expected) return false;
}
}
return openings.isEmpty();
}
public static boolean baseline(String s) {
validate(s);
String remaining = s;
while (true) {
String next = remaining.replace("()", "").replace("[]", "").replace("{}", "");
if (next.length() == remaining.length()) return next.isEmpty();
remaining = next;
}
}
}
Read the meaningful blocks
Validate before structural checks
An invalid character anywhere produces the documented alphabet exception rather than being silently ignored after an early mismatch.
Short-circuit empty before pop
The empty guard prevents a stack exception on a structurally invalid but legal-alphabet string such as ).
Use ArrayDeque
Deque push/pop represents the LIFO requirement without the legacy synchronized Stack class. Array growth gives amortized constant-time pushes.
Complexity
O(n) total time including validation and amortized deque operations, with O(n) worst-case auxiliary stack space. Return storage is one boolean.
Repeated pair erasure may scan and copy a shrinking string O(n) times, giving O(n²) time. A constant number of live strings uses O(n) live space, though cumulative allocations can be quadratic. Deep large cases exercise only the optimized method.
Exact-state walkthroughs
Reveal normal and boundary traces
Match nested types in reverse opening order
Input: "([{}])" · Result: true
Step 1 of 8: Begin with no unmatched openings.
The stack is shown bottom to top and represents exactly pending opening types.
- 0: "("
- 1: "["
- 2: "{"
- 3: "}"
- 4: "]"
- 5: ")"
Empty at this step.
| Variable | Value |
|---|---|
| text | "([{}])" |
| stackValues | [] |
See the affected Java block
1 import java.util.ArrayDeque; 2 public final class Solution { 3 private static void validate(String s) { 4 for (int i = 0; i < s.length(); i++) if ("()[]{}".indexOf(s.charAt(i)) < 0) throw new IllegalArgumentException("brackets only"); 5 } 6 public static boolean isValid(String s) { 7 validate(s); 8 ArrayDeque<Character> openings = new ArrayDeque<>(); 9 for (int i = 0; i < s.length(); i++) { 10 char symbol = s.charAt(i); 11 if (symbol == '(' || symbol == '[' || symbol == '{') openings.push(symbol); 12 else { 13 char expected = symbol == ')' ? '(' : symbol == ']' ? '[' : '{'; 14 if (openings.isEmpty() || openings.pop() != expected) return false; 15 } 16 } 17 return openings.isEmpty(); 18 } 19 public static boolean baseline(String s) { 20 validate(s); 21 String remaining = s; 22 while (true) { 23 String next = remaining.replace("()", "").replace("[]", "").replace("{}", ""); 24 if (next.length() == remaining.length()) return next.isEmpty(); 25 remaining = next; 26 } 27 } 28 } 29
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with no unmatched openings.
The stack is shown bottom to top and represents exactly pending opening types.
- text
"([{}])"- stackValues
[]
- Push an unmatched opening.
The newest opening must be the next one closed.
- text
"([{}])"- index
0- symbol
"("- stackValues
["("]
- Push an unmatched opening.
The newest opening must be the next one closed.
- text
"([{}])"- index
1- symbol
"["- stackValues
["(","["]
- Push an unmatched opening.
The newest opening must be the next one closed.
- text
"([{}])"- index
2- symbol
"{"- stackValues
["(","[","{"]
- Close the latest opening of the required type.
Java consumes the top when present before comparing its type; a missing or wrong type proves invalid nesting.
- text
"([{}])"- index
3- symbol
"}"- expected
"{"- popped
"{"- matched
true- stackValues
["(","["]
- Close the latest opening of the required type.
Java consumes the top when present before comparing its type; a missing or wrong type proves invalid nesting.
- text
"([{}])"- index
4- symbol
"]"- expected
"["- popped
"["- matched
true- stackValues
["("]
- Close the latest opening of the required type.
Java consumes the top when present before comparing its type; a missing or wrong type proves invalid nesting.
- text
"([{}])"- index
5- symbol
")"- expected
"("- popped
"("- matched
true- stackValues
[]
- Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
- result
true
Crossing types fail at the top
Input: "([)]" · Result: false
Step 1 of 5: Begin with no unmatched openings.
The stack is shown bottom to top and represents exactly pending opening types.
- 0: "("
- 1: "["
- 2: ")"
- 3: "]"
Empty at this step.
| Variable | Value |
|---|---|
| text | "([)]" |
| stackValues | [] |
See the affected Java block
1 import java.util.ArrayDeque; 2 public final class Solution { 3 private static void validate(String s) { 4 for (int i = 0; i < s.length(); i++) if ("()[]{}".indexOf(s.charAt(i)) < 0) throw new IllegalArgumentException("brackets only"); 5 } 6 public static boolean isValid(String s) { 7 validate(s); 8 ArrayDeque<Character> openings = new ArrayDeque<>(); 9 for (int i = 0; i < s.length(); i++) { 10 char symbol = s.charAt(i); 11 if (symbol == '(' || symbol == '[' || symbol == '{') openings.push(symbol); 12 else { 13 char expected = symbol == ')' ? '(' : symbol == ']' ? '[' : '{'; 14 if (openings.isEmpty() || openings.pop() != expected) return false; 15 } 16 } 17 return openings.isEmpty(); 18 } 19 public static boolean baseline(String s) { 20 validate(s); 21 String remaining = s; 22 while (true) { 23 String next = remaining.replace("()", "").replace("[]", "").replace("{}", ""); 24 if (next.length() == remaining.length()) return next.isEmpty(); 25 remaining = next; 26 } 27 } 28 } 29
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with no unmatched openings.
The stack is shown bottom to top and represents exactly pending opening types.
- text
"([)]"- stackValues
[]
- Push an unmatched opening.
The newest opening must be the next one closed.
- text
"([)]"- index
0- symbol
"("- stackValues
["("]
- Push an unmatched opening.
The newest opening must be the next one closed.
- text
"([)]"- index
1- symbol
"["- stackValues
["(","["]
- Reject a missing or mismatched opening.
Java consumes the top when present before comparing its type; a missing or wrong type proves invalid nesting.
- text
"([)]"- index
2- symbol
")"- expected
"("- popped
"["- matched
false- stackValues
["("]
- Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
- result
false
Test the contract
Input:
""
Output:trueEmpty sequence.
Input:
")("
Output:falsePremature closing bracket.
Input:
"(("
Output:falseUnmatched suffix obligations.
Input:
"( )"
Output:IllegalArgumentExceptionSpaces are outside the declared alphabet.
Common mistakes and counterexamples
Use one counter for all bracket types
Counterexample: ([)] has balanced counts but crossing types.
Retain opening types in nesting order.
Pop without checking empty
Counterexample: A first symbol ) has no opening.
Return false before accessing the empty stack.
Ignore leftover openings
Counterexample: (( contains no bad closer but is incomplete.
Require an empty stack at the end.
Follow-ups
Return the first invalid position.
A mismatching or premature closer gives an immediate index. If only openings remain at end, define whether to report end-of-input or the oldest unmatched opening; retain indices to support that policy.
Support ordinary text between brackets.
Specify whether non-bracket characters are ignored, tokenized, or rejected. The current API rejects them, so broaden validation and tests deliberately rather than silently skipping them.
Use only one bracket type.
A nonnegative running balance with final zero suffices for round brackets alone. Multiple types require more state because balance cannot encode nesting type order.