Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Balanced Parentheses

Easy
0/40
Average time to solve is 17m
profile
Contributed by
1 upvote

Problem statement

Given an expression string 's', check whether the pairs and orders of {}, (), and [] brackets are correct. If the brackets are balanced, the function should return true; otherwise, it should return false.


Example:
's' = {[()]}, the function should return true since all brackets are correctly balanced. 

However, if the string 's' =  "{[()})", the expected behavior for the function is to return false. 

This is because the closing square bracket ']' is mismatched with the closing parenthesis ')', resulting in unbalanced brackets.
Detailed explanation ( Input/output format, Notes, Images )
Input format:
The only line contains a string ‘s’.
Output Format:
The output contains a string 'true' or 'false'.
Note:-
You don’t need to print anything. Just implement the given function.
Sample Input 1:
[{}()]
Sample Output 1:
true
Explanation Of Sample Input 1:
's' = [{}()]
Since all the brackets are properly balanced, therefore output is ‘true’.
Sample Input 2:
[(])
Sample Output 2:
false
Explanation Of Sample Input 2:
's' = [(])
Since ‘(‘ bracket is not balanced properly inside “[]” brackets, therefore output is ‘false’.
Constraints:
1 <= 's'.length <= 5*10^4
Time Limit: 1 sec
Hint

Try using stack.

Approaches (1)
Stack based approach

Approach:

 

The approach uses a stack to keep track of opening brackets encountered. Whenever a closing bracket is encountered, it is matched with the top of the stack. If the brackets are balanced, the stack should be empty at the end.

 

Algorithm:

  • create a stack ‘st’
  • for each character ‘ch’ in ‘s’:
    • if ‘st’ is empty and ‘ch’ is a closing bracket:
      • return false
    • else if ‘ch’ is an opening bracket:
      • push it onto ‘st’
    • else if ‘ch’ is a closing bracket:
      • if the top of ‘st’ contains the corresponding opening bracket :
        • pop the opening bracket from ‘st’
      • else:
        • return false
  • if ‘st’ is empty:
    • return true
  • else:
    • return false
Time Complexity

O(N), where ‘N’ is the length of the input string ‘s’.

 

The time complexity of this algorithm is O(N), where ‘N’ is the length of the input string ‘s’. This is because the function iterates over each character in the string exactly once.

Space Complexity

O(N), where ‘N’ is the length of the input string ‘s’.

 

The space complexity depends on the maximum number of opening brackets encountered in the string. In the worst case, if all characters in the string are opening brackets, the stack ‘st’ will contain all of them. Therefore, the space complexity is O(N) in the worst case where ‘N’ is the size of string ‘s’.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Balanced Parentheses
All tags
Sort by
Search icon

Interview problems

BALANCED PARENTHSES BY PYTHON(ALL TEST CASE PASSED)

from typing import List

 

def isBalanced(S: str) -> bool:

    stack = []

    

    bracket_map = {')': '(', '}': '{', ']': '['}

    

    for char in S:

        if char in bracket_map.values():  

            stack.append(char)

        elif char in bracket_map:  

            if stack and stack[-1] == bracket_map[char]:

                stack.pop()  

            else:

                return False  

    

    return not stack

 

18 views
0 replies
0 upvotes

Interview problems

balanced parenthese

bool isBalanced(string S){

    stack<char> st;

    int count = 0;

    int n = S.length();

    for(int i=0;i<n;i++)

    {

        if(S[i]=='(' || S[i]=='{' || S[i]=='[')

        {

            st.push(S[i]);

            count++;

        }

        else

        {

            if(S[i]==')' && !st.empty() && st.top()=='(')

            {

                st.pop();

                count--;

            }

            else if(S[i]=='}' && !st.empty() && st.top()=='{')

            {

                st.pop();

                count--;

            }

            else if(S[i]==']' && !st.empty() && st.top()=='[')

            {

                st.pop();

                count--;

            }

        }

    }

    if(count==0)

    {

        return true;

    }

    return false;

}

61 views
0 replies
0 upvotes

Interview problems

C++ Solution

bool isBalanced(string s){

    // Write your code here.

    stack<char> stk;

    for(int i=0;i<s.length();i++){

        char ch = s[i];

        if(ch == '(' || ch == '{' || ch == '[') stk.push(ch);

        else{

            if(!stk.empty()){

              if ((ch == ')' && stk.top() == '(') || (ch == '}' && stk.top() == '{') || (ch == ']' && stk.top() == '[')){

                      stk.pop();

                  }

              else return false;

            }

            else return false;

        }

    }

    if(stk.empty()) return true;

    else return false;

 

}

89 views
0 replies
2 upvotes
Full screen
Console