Balanced Parentheses
Ramayana — Valmiki's Sacred Verse — Every Opening Bracket Finds Its Closing Match
यः उद्घाटयति तस्य निर्गमः आवश्यकः। यत्र युगलं पूर्णं — तत्र सन्तुलनम्॥
*Whatever opens must find its closing. Where every pair is complete — there is balance.*
The Story
Given a string of brackets `()[]{}`, determine if the brackets are valid (balanced).
Valid: `"()"`, `"()[]{}"` Invalid: `"(]"`, `"([)]"`, `"{[]"`
Valmiki composed the Ramayana with nested verse structures — every opening stanza (opening bracket) had to be closed by its corresponding closing stanza in perfect order. Mismatched closings destroyed the sacred structure.
The stack approach is the classic solution: - For OPENING brackets `( [ {`: push the corresponding CLOSING bracket onto the stack - For CLOSING brackets `) ] }`: check if stack is non-empty AND stack top equals current character. If yes: pop. If no: INVALID. - At end: stack must be EMPTY (all opened brackets were closed)
Trace `"()[]{}"`: - '(': push ')'. Stack=[)] - ')': top=')'==')'. Pop. Stack=[] - '[': push ']'. Stack=[] - ']': top=']'. Pop. Stack=[] - '{': push '}'. Stack=[}] - '}': top='}'. Pop. Stack=[] Stack empty → valid ✓
Trace `"([)]":` - '(': push ')'. Stack=[)] - '[': push ']'. Stack=[), ]] - ')': top=']'≠')' → INVALID ✗
"Push the EXPECTED closing bracket," Valmiki instructed. "Then when you see a closing bracket, just check if it's what was expected. This avoids the matching map entirely."
The Repeated Reduction
Repeatedly replace `()`, `[]`, `{}` with empty string until no more replacements. If string is empty → valid. O(n²) — multiple passes.
public boolean isValidBruteForce(String s) {
while (s.contains("()") || s.contains("[]") || s.contains("{}")) {
s = s.replace("()", "").replace("[]", "").replace("{}", "");
}
return s.isEmpty();
}Valmiki's Expected-Closing Stack
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '[') stack.push(']');
else if (c == '{') stack.push('}');
else {
// Closing bracket: must match expected
if (stack.isEmpty() || stack.pop() != c) return false;
}
}
return stack.isEmpty();
}Step-by-Step Walkthrough
"]"
']' → stack empty → return false ✅
"((("
'(' push ')': [)]
'(' push ')': [),)]
'(' push ')': [),),)]
End: not empty → false ✅Deep Insight
**Push the EXPECTED closer, not the opener itself.** This simplifies the check: we just compare the current closing bracket to the top — no need for a separate lookup map.
**Three failure conditions:** 1. Closing bracket with empty stack (more closers than openers) 2. Closing bracket doesn't match stack top (wrong type of bracket) 3. Non-empty stack at end (more openers than closers)
**This is the canonical stack problem.** Balanced parentheses validates the LIFO order of nested structures — the same property used in compilers, code editors, and expression evaluators.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Repeated string replacements |
| Optimal | O(n) | O(n) | Single pass, stack size at most n/2 |
Pattern Recognition
✅ Push expected CLOSER for each opener ✅ For closer: if empty or top≠c → false ✅ End check: stack must be empty ✅ Three types of brackets handled uniformly **LeetCode Trigger Phrases:** → "valid parentheses" → "balanced brackets" → "matching opening and closing"
Bhagavad Gita 8.6
यं यं वापि स्मरन्भावं त्यजत्यन्ते कलेवरम्। तं तमेवैति कौन्तेय सदा तद्भावभावितः॥
Whatever state of being one remembers when leaving the body at the time of death, to that state alone will one go, O son of Kunti, always shaped by that thought.
Connection: Every opening bracket creates an expectation — a specific closing bracket must eventually come. The stack holds this expectation throughout the traversal, just as the soul carries its last thought through time. When the closing bracket arrives, if it matches the expectation perfectly, the pair is resolved. If not, the balance is broken. Perfect structural balance, like perfect spiritual balance, requires each opening to be answered by exactly the right closing.