Balanced Parentheses
Check if a string of parentheses (like "(), {}, []") is balanced. A balanced expression means every opening bracket has a corresponding closing bracket in the correct order.
Algorithm:
1. Use a stack.
2. For each character:
- If it's an opening bracket, push onto stack.
- If it's a closing bracket, check if stack is empty or top doesn't match; if so, return false.
- Otherwise, pop the top.
3. After processing all characters, stack should be empty.
Java implementation:
public static boolean isBalanced(String s) {
Stack stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
return false;
}
}
}
return stack.isEmpty();
}
// Example: "{[()]}" → true, "{[(])}" → false
Two Minute Drill
- Balanced parentheses check uses stack.
- Push opening brackets; on closing, compare with top.
- Must match and stack must be empty at end.
- Time O(n), space O(n).
- Classic interview problem, extension includes multiple bracket types.
Need more clarification?
Drop us an email at career@quipoinfotech.com