Definition
- Valid Parentheses – verify that every opening bracket
(,[,{has a correctly typed and correctly ordered closing bracket),],}. - Stack approach – push each opener; on each closer, pop and compare against the expected opener from a map.
- Two failure conditions – empty stack on a closer means unmatched close; non-empty stack at the end means unmatched opens.
- Complexity – O(n) time because each character is pushed and popped at most once; O(n) space worst case.
- Best practice – use
ArrayDequethrough theDequeinterface, not the legacy synchronizedStackclass.
Imagine Rajesh at National Bank of India opening nested approval requests. He opens a loan request, then inside it opens a document verification, then a signature request. Each request he writes on a sticky note and places on top of a pile. When a request closes, the one on top must be the most recently opened and the same type. If a signature request tries to close while a document request is on top, the paperwork is rejected.
Understanding the Concepts
What is the Valid Parentheses problem?
Given a string containing only round, square, and curly brackets, determine whether every opening bracket is closed by a matching type in the correct nesting order. The LIFO discipline of a stack makes it the natural tool: the bracket that must close first is always the one most recently opened.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
public class ValidParentheses {
public static boolean isValid(String s) {
if (s.length() % 2 != 0) return false; // odd-length shortcut
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) {
stack.push(c);
} else if (pairs.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
return false;
}
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isValid("()[]{}")); // true
System.out.println(isValid("({[]})")); // true
System.out.println(isValid("(]")); // false
System.out.println(isValid("(((")); // false
}
}
true
true
false
false
Why does this problem use a stack?
Brackets must close in the reverse order they opened. Open round, then square, then curly means you must close curly first, then square, then round. This reverse ordering is LIFO, and a stack enforces it structurally. No other data structure gives you the most recently pushed element on every access.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class WhyStackForBrackets {
public static void main(String[] args) {
Deque<String> approvals = new ArrayDeque<>();
approvals.push("Loan opened");
approvals.push("Document opened");
approvals.push("Signature opened");
// Must close in reverse order
System.out.println(approvals.pop()); // Signature
System.out.println(approvals.pop()); // Document
System.out.println(approvals.pop()); // Loan
}
}
Signature opened
Document opened
Loan opened
How does the algorithm work step by step?
Scan left to right. On each opener, push it. On each closer, check the stack is not empty and pop the top. Compare the popped opener to the expected match from the map. If anything fails, return false. After the scan, return stack.isEmpty().
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
public class StepByStep {
public static void main(String[] args) {
String input = "{[()]}";
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (pairs.containsValue(c)) {
stack.push(c);
System.out.println("i=" + i + " push '" + c + "'");
} else {
char top = stack.pop();
System.out.println("i=" + i + " pop '" + top + "' match '" + pairs.get(c) + "' -> " + (top == pairs.get(c)));
}
}
System.out.println("Valid: " + stack.isEmpty());
}
}
i=0 push '{'
i=1 push '['
i=2 push '('
i=3 pop '(' match '(' -> true
i=4 pop '[' match '[' -> true
i=5 pop '{' match '{' -> true
Valid: true
What are the two failure conditions?
First, a closer arrives when the stack is empty, meaning there is no opener to match. Second, the scan finishes with openers still on the stack, meaning some brackets were never closed. Both checks are essential. Missing the final emptiness check wrongly accepts strings like "(((".
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
public class FailureConditions {
public static String check(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (pairs.containsValue(c)) stack.push(c);
else if (pairs.containsKey(c)) {
if (stack.isEmpty()) return "Fail: unmatched closer at " + i;
if (stack.pop() != pairs.get(c)) return "Fail: type mismatch at " + i;
}
}
return stack.isEmpty() ? "Valid" : "Fail: " + stack.size() + " unmatched openers";
}
public static void main(String[] args) {
System.out.println(check(")(")); // unmatched closer
System.out.println(check("(((")); // unmatched openers
System.out.println(check("(]")); // type mismatch
}
}
Fail: unmatched closer at 0
Fail: 3 unmatched openers
Fail: type mismatch at 1
What are the edge cases?
Empty string is valid. Odd-length string is always invalid. Single opener or single closer is invalid. Deeply nested valid strings and sequential valid pairs both pass.
package com.bank.core;
public class EdgeCasesDemo {
static boolean isValid(String s) {
if (s.length() % 2 != 0) return false;
java.util.Deque<Character> st = new java.util.ArrayDeque<>();
var p = java.util.Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (p.containsValue(c)) st.push(c);
else if (p.containsKey(c) && (st.isEmpty() || st.pop() != p.get(c))) return false;
}
return st.isEmpty();
}
public static void main(String[] args) {
System.out.println("Empty: " + isValid("")); // true
System.out.println("Odd: " + isValid("(()")); // false
System.out.println("Deep: " + isValid("(((())))")); // true
System.out.println("Seq: " + isValid("()[]{}")); // true
}
}
Empty: true
Odd: false
Deep: true
Seq: true
What are common mistakes?
Forgetting the final stack.isEmpty() check is the most common bug: it wrongly accepts all-opener strings. Another mistake is not checking for an empty stack before popping, which throws NoSuchElementException. A third is comparing Character wrapper objects with == beyond the cached range; using char primitives avoids this.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class CommonBugs {
// WRONG: missing final isEmpty check
static boolean buggy(String s) {
Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') st.push(c);
else { if (st.isEmpty()) return false; st.pop(); }
}
return true; // BUG: should be st.isEmpty()
}
public static void main(String[] args) {
System.out.println("Buggy accepts '(((': " + buggy("(((")); // true (wrong!)
}
}
Buggy accepts '(((': true
How is this applied in banking?
At National Bank of India, fee formulas use nested brackets like {(base + [tax * rate]) * discount}. A parentheses validator runs before the expression parser. If the brackets are unbalanced, the formula is rejected and logged, protecting the calculation engine from evaluating corrupt expressions.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
public class FeeFormulaValidator {
private static final Map<Character, Character> PAIRS =
Map.of(')', '(', ']', '[', '}', '{');
public static boolean validate(String formula) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : formula.toCharArray()) {
if (PAIRS.containsValue(c)) stack.push(c);
else if (PAIRS.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != PAIRS.get(c)) return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(validate("{(base + [tax * rate]) * discount}")); // true
System.out.println(validate("{(base + [tax * rate) * discount}")); // false
}
}
true
false
What about time and space complexity?
Time is O(n) because each character is visited once, pushed at most once, and popped at most once. Space is O(n) in the worst case where every character is an opener. In practice the stack only grows to the maximum nesting depth.
package com.bank.core;
public class Complexity {
public static void main(String[] args) {
System.out.println("Time: O(n) - single pass, each char pushed/popped at most once");
System.out.println("Space: O(n) worst case - all openers like '(((((('");
System.out.println("Best case: O(1) early exit on odd length or first mismatch");
}
}
Time: O(n) - single pass, each char pushed/popped at most once
Space: O(n) worst case - all openers like '(((((('
Best case: O(1) early exit on odd length or first mismatch
What should a senior engineer know?
This technique extends directly to matching HTML/XML tags, validating nested expressions, and checking balanced quotes in parsers. The map-based matching is extensible: adding angle brackets or custom delimiters is a one-line change. Always prefer ArrayDeque over Stack because Stack extends Vector with unnecessary synchronization.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
public class ExtensibleMatcher {
// Add custom delimiters with one extra map entry
private static final Map<Character, Character> PAIRS = Map.of(
')', '(', ']', '[', '}', '{', '>', '<'
);
public static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (PAIRS.containsValue(c)) stack.push(c);
else if (PAIRS.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != PAIRS.get(c)) return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isValid("<{[()]}>")); // true
}
}
true
Visual Overview
Validation Walk: "{[()]}"
────────────────────────
Char Action Stack (top left)
──── ───────────── ────────────────
{ push [ { ]
[ push [ [ { ]
( push [ ( [ { ]
) pop ( match ) [ [ { ]
] pop [ match ] [ { ]
} pop { match } [ ] (empty)
Stack empty → VALID
Failure Walk: "(]" ────────────────── Char Action Stack ──── ────────────────── ───── ( push [ ( ] ] pop ( expect [ → MISMATCH → INVALID
Key Takeaway
Valid Parentheses checks whether a string of round, square, and curly brackets is balanced and properly nested. The approach is to scan the string once, push every opening bracket onto a stack, and on every closing bracket pop the top and confirm it is the matching opener using a small map. The two failure conditions are an empty stack when a closer arrives and a non-empty stack after the full scan, and both checks together are what make the solution correct.
The algorithm runs in O(n) time because each character is pushed and popped at most once, with O(n) worst-case space. I always use ArrayDeque rather than the legacy Stack class because Stack extends Vector and synchronizes every call, adding pointless overhead. I also add the odd-length shortcut: a string of odd length can never balance, so I reject it before the loop starts.
In my banking project at the National Bank of India, I used this as a fast pre-check on fee-calculation formulas with nested bracket delimiters. A malformed formula is rejected before the expression parser runs, protecting the engine from corrupt input and giving the operations team a clean audit trail of every rejected formula.
The technique extends directly to matching HTML/XML tags, validating nested expressions, and checking balanced quotes in production parsers. The map-based matching makes it trivial to add new bracket types with a single extra entry, so the same validator adapts to any delimiter scheme.
Remember one sentence: push every opener, pop and type-match on every closer, and the string is valid only if the stack ends empty.
---