Solution: Balanced Parentheses

Grokking Data Structures & Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Balanced Parentheses

Table of Contents

Contents are not accessible

Problem Statement

Given a string s containing (, ), [, ], {, and } characters. Determine if a given string of parentheses is balanced.

A string of parentheses is considered balanced if every opening parenthesis has a corresponding closing parenthesis in the correct order.

Example 1:

Input: String s = "{[()]}";
Expected Output: true
Explanation: The parentheses in this string are perfectly balanced. Every opening parenthesis '{', '[', '(' has a corresponding closing parenthesis '}', ']', ')' in the correct order.

Example 2:

Input: string s = "{[}]";
Expected Output: false
Explanation: The brackets are not balanced in this string. Although it contains the same number of opening and closing brackets for each type, they are not correctly ordered. The ']' closes '[' before '{' can be closed by '}', and similarly, '}' closes '{' before '[' can be closed by ']'.

Example 3:

Input: String s = "(]";
Expected Output: false
Explanation: The parentheses in this string are not balanced. Here, ')' does not have a matching opening parenthesis '(', and similarly, ']' does not have a matching opening bracket '['.

Constraints:

1 <= s.length <= 10<sup>4</sup>
s consists of parentheses only '()[]{}'.

Solution

To solve this problem, we use a stack data structure. As we traverse the string, each time we encounter an opening parenthesis ('(', '{', or '['), we push it onto the stack. When we find a closing parenthesis (')', '}', or ']'), we check if it matches the type of the opening parenthesis at the top of the stack. If it matches, we pop the top element from the stack; if not, or if the stack is empty when we find a closing parenthesis, the string is not balanced, and we return false.

After processing the entire string, if the stack is empty, it means all parentheses were properly closed and nested, so we return true. Otherwise, we return false.

Here is a step-by-step algorithm:

Initialize an empty Stack.
Iterate over the string of parentheses.
- If the current character is an opening parenthesis, push it onto the Stack.
- If the current character is a closing parenthesis, check the top of the Stack.
  - If the Stack is empty, then the string is not balanced (there is a closing parenthesis without a matching opening parenthesis), so return false.
  - If the top of the Stack is the matching opening parenthesis, pop it off the Stack.
  - If the top of the Stack is not the matching opening parenthesis, then the string is not balanced, so return false.
After checking all parentheses, if the Stack is empty, then the string is balanced, so return true. If the Stack is not empty, then there are unmatched opening parentheses, so the string is not balanced, return false.

Algorithm Walkthrough

Let's consider the input "{[()]}", and observe how algorithm works.

Initialization:

Start with an empty stack.

Iteration 1: Character = '{'

Stack before operation: []
Since '{' is an opening bracket, push it onto the stack.

Iteration 2: Character = '['

Stack before operation: ['{']
Since '[' is an opening bracket, push it onto the stack.

Iteration 3: Character = '('

Stack before operation: ['{', '[']
Since '(' is an opening bracket, push it onto the stack.

Iteration 4: Character = ')'

Stack before operation: ['{', '[', '(']
')' is a closing bracket. The top of the stack is '(', which is the corresponding opening bracket for ')'. So, pop '(' from the stack.

Iteration 5: Character = ']'

Stack before operation: ['{', '[']
']' is a closing bracket. The top of the stack is '[', which is the corresponding opening bracket for ']'. So, pop '[' from the stack.

Iteration 6: Character = '}'

Stack before operation: ['{']
'}' is a closing bracket. The top of the stack is '{', which is the corresponding opening bracket for '}'. So, pop '{' from the stack.

Final Check:

After processing all characters, check the stack.
The stack is empty, indicating that all opening brackets were properly matched and closed.
Therefore, the input string "{[()]}" is valid with properly balanced parentheses.

1 of 8

Code

Here is how you can implement this algorithm:

Python3

. . . .

In this code, the isValid function checks if a given string of parentheses s is balanced by using a Stack. It pushes any opening parentheses onto the Stack and pops off the Stack whenever a closing parenthesis is encountered. If the Stack is empty at the end, then the string is balanced.

Complexity Analysis

Time Complexity

Single pass: The algorithm iterates through each character of the input string exactly once. This gives us a time complexity of $O(N)$ , where N is the length of the input string.
Stack operations: Each push and pop operation on the stack is done in constant time, $O(1)$ , because stacks provide constant time access for these operations.

Overall time complexity: $O(N)$ .

Space Complexity

Stack space: In the worst case, the stack could store all opening parentheses (if the string contains only opening brackets), meaning the space used by the stack is proportional to the length of the input string. Therefore, the space complexity is $O(N)$ , where N is the length of the input string.
Additional variables: The algorithm uses a few additional variables like c and top, which require constant space, $O(1)$ .

Overall space complexity: $O(N)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible