Balanced Parentheses Editorial

Practice Problem Link: Balanced Parentheses

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a string with just the six characters - ‘(’, ‘)’, ‘{’, ‘}', ‘[’ and ‘]’. Determine if the string is balanced.

Approach

The approach for this problem is pretty simple. 

• Declare an empty stack.
• Traverse the string and whenever an opening bracket is encountered, insert it into the stack.
• When a closing bracket is encountered, check if the last bracket in the stack matches the current closing bracket. If not then return false otherwise remove the last bracket from the stack.
• After traversing the string, if the stack is empty return true otherwise return false.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

bool isBalancedParentheses(string str) {
    int n = str.size();
	stack<char> openingBrackets;
	for (int i = 0; i < n; i++) {
		if (str[i] == '(' || str[i] == '{' || str[i] == '[') {
			openingBrackets.push(str[i]);
		} else {
			if (openingBrackets.empty()) {
				return false;
			}
			if (str[i] == ')') {
				char last = openingBrackets.top();
				openingBrackets.pop();
				if (last != '(') {
					return false;
				}
			}
			if (str[i] == '}') {
				char last = openingBrackets.top();
				openingBrackets.pop();
				if (last != '{') {
					return false;
				}
			}
			if (str[i] == ']') {
				char last = openingBrackets.top();
				openingBrackets.pop();
				if (last != '[') {
					return false;
				}
			}
		}
	}
	return openingBrackets.empty();
}

Java

class Solution {
	boolean isBalancedParentheses(String str) {
	    int n = str.length();
		Stack<Character> openingBrackets = new Stack<>();
		for (int i = 0; i < n; i++) {
			if (str.charAt(i) == '(' || str.charAt(i) == '{' || str.charAt(i) == '[') {
				openingBrackets.push(str.charAt(i));
			} else {
				if (openingBrackets.empty()) {
					return false;
				}
				if (str.charAt(i) == ')') {
					char last = openingBrackets.peek();
					openingBrackets.pop();
					if (last != '(') {
						return false;
					}
				}
				if (str.charAt(i) == '}') {
					char last = openingBrackets.peek();
					openingBrackets.pop();
					if (last != '{') {
						return false;
					}
				}
				if (str.charAt(i) == ']') {
					char last = openingBrackets.peek();
					openingBrackets.pop();
					if (last != '[') {
						return false;
					}
				}
			}
		}
		return openingBrackets.isEmpty();
	}
}