Balanced Bracket Validator — Problem Statement & Solution Guide
Problem Description
You are given a string s that contains only the characters '(' , ')' , '{' , '}' , '[' and ']'. Determine whether s forms a correctly nested bracket sequence. A sequence is correct when each opening bracket is paired with a closing bracket of the same type and the pairs appear in a properly ordered, non‑overlapping fashion. Return true if the entire string is correct; otherwise return false. Your solution must examine the characters in a single left‑to‑right pass and may use a stack to keep track of pending openings, achieving O(n) time and O(n) auxiliary space where n is the length of s.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Balanced Bracket Validator"
WHY DOES IT MATTER?
Bracket validation appears in compilers, interpreters, and any syntax‑checking tool; mastering the stack pattern ensures you can reason about nested structures efficiently.
OPTIMIZATION CHALLENGE
Recognizing that only the most recent unmatched opening bracket matters reduces the problem from quadratic pair‑search to a linear scan with constant‑time checks per character.
REAL-WORLD CONNECTION
Think of a call stack in a distributed microservice: each request pushes a context, and responses must unwind in reverse order, mirroring how opening brackets push and closing brackets pop.
During an interview, write the push/pop logic first, then immediately add a map of closing→opening to avoid tangled conditionals; this keeps the code readable under pressure.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The balanced‑bracket problem is a classic example of validating a context‑free language using a deterministic push‑down automaton, which in practice translates to a stack. A naive solution might try to match every opening bracket with every closing one, leading to O(n^2) time or exponential recursion because the algorithm would repeatedly scan the string for pairs. The optimal paradigm leverages the LIFO property of a stack: each time we see an opening symbol we push it, and each time we see a closing symbol we pop and verify the types match, guaranteeing a single linear pass. This approach works because well‑formed bracket sequences are inherently nested, and the most recent unmatched opening bracket must be closed first, which is exactly what a stack enforces.
Interview Questions on This Problem
Q1How would you modify the algorithm to return the index of the first mismatched bracket instead of a boolean?
Maintain the current index while iterating; when a closing bracket does not match the top of the stack, return that index. If the stack is non‑empty after the loop, return the index of the first element left in the stack (its stored position).
Q2Can you solve the balanced bracket validation without using extra space?
Yes, by using two counters for parentheses only, but for three types of brackets you need a stack; however, you can simulate a stack with the input string itself if you are allowed to modify it in‑place, achieving O(1) extra space.
Q3What is the time‑space trade‑off if you pre‑compute a map of closing to opening brackets versus using a series of if‑else statements?
A hash map gives O(1) lookup and keeps the code clean, with negligible extra space (constant size). Using if‑else incurs no extra data‑structure space but adds constant‑time branching; both are O(1) per operation, so the overall complexity remains O(n) time and O(n) stack space.
Examples
Input
([]){}Output
true
Explanation: Read '(' → push. Read '[' → push. Read ']' matches top '[' → pop. Read ')' matches top '(' → pop. Read '{' → push. Read '}' matches top '{' → pop. Stack empty at end, so the string is balanced.
Input
([)]
Output
false
Explanation: Read '(' → push. Read '[' → push. Read ')' does not match top '[' (expected ']'), so the sequence is invalid immediately.
Input
{[()()]}Output
true
Explanation: Push '{', push '[', push '(' then ')' matches '(' → pop, push '(' then ')' matches '(' → pop, ']' matches '[' → pop, '}' matches '{' → pop. Stack empty, therefore balanced.
Constraints
- 1 <= s.length <= 100000
- s contains only the characters '(' , ')' , '{' , '}' , '[' and ']'
- The algorithm must run in O(s.length) time and use O(s.length) extra space
Optimal Approach & Strategy
Use a single pass with a stack: push opening brackets, pop and compare on closing brackets, and ensure the stack is empty at the end.
Brute Force Approach
Repeatedly scan the string for any adjacent matching pair and remove it until no pairs remain, which can require many passes over the data.
Verified Code Solutions
function isValid(s){\n const map={')':'(','}':'{',']':'['};\n const stack=[];\n for(const ch of s){\n if(map[ch]){\n if(stack.length===0||stack[stack.length-1]!==map[ch]) return false;\n stack.pop();\n }else{\n stack.push(ch);\n }\n }\n return stack.length===0;\n}\n\nfunction main(){\n const fs=require('fs');\n const input=fs.readFileSync(0,'utf8').trim();\n const result=isValid(input);\n console.log(result?\"true\":\"false\");\n}\nmain();\n#include <bits/stdc++.h>\nusing namespace std;\n\nbool isValid(const string& s) {\n unordered_map<char,char> mp={{')','('},{']','['},{'}','{'}};\n stack<char> st;\n for(char c:s){\n if(mp.count(c)){\n if(st.empty()||st.top()!=mp[c]) return false;\n st.pop();\n }else{\n st.push(c);\n }\n }\n return st.empty();\n}\n\nint main(){\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n string s;\n if(!(cin>>s)) return 0;\n cout << (isValid(s) ? \"true\" : \"false\");\n return 0;\n}\nimport java.io.*;\nimport java.util.*;\npublic class Main {\n public static boolean isValid(String s){\n Map<Character,Character> map=new HashMap<>();\n map.put(')', '(');\n map.put(']', '[');\n map.put('}', '{');\n Deque<Character> stack=new ArrayDeque<>();\n for(char c: s.toCharArray()) {\n if(map.containsKey(c)) {\n if(stack.isEmpty() || stack.peek()!=map.get(c)) return false;\n stack.pop();\n } else {\n stack.push(c);\n }\n }\n return stack.isEmpty();\n }\n public static void main(String[] args) throws Exception {\n BufferedReader br=new BufferedReader(new InputStreamReader(System.in));\n String s=br.readLine();\n System.out.print(isValid(s)?\"true\":\"false\");\n }\n}\ndef is_valid(s):\n mapping={')':'(','}':'{',']':'['}\n stack=[]\n for ch in s:\n if ch in mapping:\n if not stack or stack[-1]!=mapping[ch]:\n return False\n stack.pop()\n else:\n stack.append(ch)\n return not stack\n\nif __name__=='__main__':\n import sys\n s=sys.stdin.read().strip()\n print('true' if is_valid(s) else 'false')\nfunction isValid(s){\n const map={')':'(','}':'{',']':'['};\n const stack=[];\n for(const ch of s){\n if(map[ch]){\n if(stack.length===0||stack[stack.length-1]!==map[ch]) return false;\n stack.pop();\n }else{\n stack.push(ch);\n }\n }\n return stack.length===0;\n}\n\nfunction main(){\n const fs=require('fs');\n const input=fs.readFileSync(0,'utf8').trim();\n const result=isValid(input);\n console.log(result?\"true\":\"false\");\n}\nmain();\nAsked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.