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

Valid Parentheses

Easy
0/40
Average time to solve is 10m
profile
Contributed by
384 upvotes
Asked in companies
OracleSwiggyAmerican Express

Problem statement

You're given a string 'S' consisting of "{", "}", "(", ")", "[" and "]" .


Return true if the given string 'S' is balanced, else return false.


For example:
'S' = "{}()".

There is always an opening brace before a closing brace i.e. '{' before '}', '(' before ').
So the 'S' is Balanced.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first and only input line contains a string 'S'.
Output format :
The only line of output contains 'Balanced' or 'Not Balanced'.
Note:
You are not required to print anything explicitly. It has already been taken care of. Just implement the given function.
Sample Input 1 :
[()]{}{[()()]()}
Sample Output 1 :
Balanced
Explanation Of the Sample Input 1 :
There is always an opening brace before a closing brace i.e. '{' before '}', '(' before '), '[' before ']'.
So the 'S' is Balanced.
Sample Input 2 :
[[}[
Sample Output 2 :
Not Balanced
Constraints:
1 <= 'N' <= 10^5

Where 'N' is the length of the input string 'S'.
Time Limit: 1 sec
Hint

Use Last-in-First-Out (LIFO) data structure and check the opening brace for every closing brace.

Approaches (1)
Stack:

Approach:

 

Make use of the stack. Traverse the string and push the current character in the stack if it is an opening brace. Else pop from the stack. If it is the corresponding starting brace for the current closing brace, then move to the next character of the string otherwise, return false.

 

If after complete traversal, if the stack is empty, then the string is balanced else, it is not balanced.

 

Algorithm:

 

  • Declare a character stack.
  • Now traverse the string.

    1-  If the current character is a starting bracket ( ‘(’ or ‘{’ or ‘[’ ), then push it to stack.

    2-  If the current character is a closing bracket ( ‘)’ or ‘}’ or ‘]’ ), then pop from stack, and if the popped character is the matching starting bracket, then fine 

     else parenthesis is not balanced.

  • After complete traversal, if there is some starting bracket left in the stack, then “not balanced”.
  • Otherwise, the string is balanced.

 

Time Complexity

O(N), Where ‘N’ is the length of the string.

 

The traversal of the string is done only once. Hence, the O(N) time complexity.

Space Complexity

O(N), Where ‘N’ is the length of the string.

 

As the maximum stack size reaches the length of the string, thus the O(N) space complexity.

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

Interview problems

using Python || Stack

def isValidParenthesis(s: str) -> bool:

    stack =[]

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

    for char in s:

        if char in match:

            stack.append(char)

        else:

            if stack:

                top=stack.pop()

                if match[top]!=char:

                    return False              

            else:

                return False

    return True if not stack else False

8 views
0 replies
0 upvotes

Interview problems

simple solution using stack in C++

bool isValidParenthesis(string s)

{

    // Write your code here.

    stack<char> str;

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

        char ch = s[i];

        if(ch=='('||ch=='{'||ch=='['){

            str.push(ch);

        }

        else{

            if (!str.empty()) {

              char top = str.top(); 

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

                str.pop();

              }

                else {

                  return false;

                }

            } 

            else {

                return false;

            }

        }

    }

    if(str.empty()){

        return true;

    }

    else{

        return false;

    }

}

44 views
0 replies
0 upvotes

Interview problems

Valid Parentheses

import java.util.*;

 

import java.util.Stack;

 

public class Solution {

 

    public static boolean isValidParenthesis(String s) {

 

        Stack<Character> sta = new Stack<>();

 

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

 

            char ch = s.charAt(i);

 

            if(ch=='{'||ch=='['||ch=='('){

 

                sta.push(ch);

 

            }

 

            else{

 

                if(ch=='}'){

 

                    if(sta.size()==0){

 

                        return false;

 

                    }

 

                    char top = sta.peek();

 

                    if(top!='{'){

 

                        return false;

 

                    }

 

                    if(top=='{'){

 

                        sta.pop();

 

                    }

 

                }

 

                else if(ch==')'){

 

                    if(sta.size()==0){

 

                        return false;

 

                    }

 

                    char top = sta.peek();

 

                    if(top!='('){

 

                        return false;

 

                    }

 

                    if(top=='('){

 

                        sta.pop();

 

                    }

 

                }

 

                else if(ch==']'){

 

                    if(sta.size()==0){

 

                        return false;

 

                    }

 

                    char top = sta.peek();

 

                    if(top!='['){

 

                        return false;

 

                    }

 

                    if(top=='['){

 

                        sta.pop();

 

                    }

 

                }

 

            }

 

        }

 

        return true;   

 

    }

 

}

11 views
0 replies
0 upvotes

Interview problems

JAVA SOLUTION || Valid Parentheses ||

import java.util.*;

import java.util.Stack;

public class Solution {

    public static boolean isValidParenthesis(String s) {

        Stack<Character> sta = new Stack<>();

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

            char ch = s.charAt(i);

            if(ch=='{'||ch=='['||ch=='('){

                sta.push(ch);

            }

            else{

                if(ch=='}'){

                    if(sta.size()==0){

                        return false;

                    }

                    char top = sta.peek();

                    if(top!='{'){

                        return false;

                    }

                    if(top=='{'){

                        sta.pop();

                    }

                }

                else if(ch==')'){

                    if(sta.size()==0){

                        return false;

                    }

                    char top = sta.peek();

                    if(top!='('){

                        return false;

                    }

                    if(top=='('){

                        sta.pop();

                    }

                }

                else if(ch==']'){

                    if(sta.size()==0){

                        return false;

                    }

                    char top = sta.peek();

                    if(top!='['){

                        return false;

                    }

                    if(top=='['){

                        sta.pop();

                    }

                }

            }

        }

        return true;   

    }

}

44 views
0 replies
0 upvotes

Interview problems

Simple python Code using dictionary

Keep a map of open brackets with closed brackets. 

Use the mapping to check next element of string with last element of array.

 

Code:

def isValidParenthesis(s: str) -> bool:
   arr=[]
   dt={'(':')','{':'}','[':']'}
   for i in s:
       if i in dt:
           arr.append(i)
       else:
           if len(arr) and i==dt[arr[-1]]:
               arr.pop()
           else:
               return False        
   return False if arr else True

 

python

20 views
0 replies
0 upvotes

Interview problems

EASY STACK APPROACH || 0 ms Beats 100.00% ✅ || C++ 🔥

bool isValidParenthesis(string s)

{

// Write your code here.

stack<char> b;

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

char ch=s[i];

if(ch=='(' || ch=='{' || ch=='['){

b.push(ch);

}

else{

if (!b.empty()) {

char top = b.top();

if ((ch == ')' && top == '(') || (ch == '}' && top == '{') ||

(ch == ']' && top == '[')){

b.pop();

}

else{

return false;

}

}

else{

return false;

}

}

}

if(b.empty()){

return true;

} else {

return false;

}

}

72 views
0 replies
0 upvotes

Interview problems

Simple concept based java solution.

import java.util.Stack;

public class Solution {
    public static boolean isValidParenthesis(String s) {
        // Write your code here.
        char[] ch = s.toCharArray();
        Stack<Character> stack= new Stack<>();
        stack.push('#');
        boolean balanced;
        if(ch[0]==')'||ch[0]=='}'||ch[0]==']')
        {
            balanced=false;
        }
        else{
        for(int i=0;i<ch.length;i++)
        {
            if(ch[i]=='{'||ch[i]=='('||ch[i]=='[')
            {
                stack.push(ch[i]);
            }
            if((ch[i]=='}')&&(stack.peek()=='{'))
            {
                stack.pop();
            }
            if((ch[i]==')')&&(stack.peek()=='('))
            {
                stack.pop();
            }
            if((ch[i]==']')&&(stack.peek()=='['))
            {
                stack.pop();
            }
        }
        if(stack.peek()=='#')
        {
            balanced= true;
        }
        else
        {
            balanced= false;
        }
        }
        return balanced;
    }
}
19 views
0 replies
0 upvotes

Interview problems

beats 95%. Easy solution using stack

#include<stack>
bool isValidParenthesis(string s)
{
    // Write your code here.
    stack<char> b;
    for(int i=0;i<s.length();i++){
        char ch=s[i];
        if(ch=='(' || ch=='{' || ch=='['){
            b.push(ch);
        }
        else{
            if (!b.empty()) {
              char top = b.top();
              if ((ch == ')' && top == '(') || (ch == '}' && top == '{') ||
                  (ch == ']' && top == '[')){
                      b.pop();
                  }
                else{
                    return false;
                }
            }
            else{
                return false;
            }
        }
    }
    if(b.empty()){
        return true;
    }
    else{
        return false;
    }
}
51 views
0 replies
0 upvotes

Interview problems

Java Easy Solution

import java.util.Stack;

 

public class Solution {

    public static boolean isValidParenthesis(String s) {

        // Write your code here.

        Stack<Character>stack=new Stack<>();

        for(char ch: s.toCharArray()){

            if(stack.isEmpty() && (ch==']'||ch==')'||ch=='}')) return false;

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

            else if((ch=='}'||ch==']'||ch==')')&& !stack.isEmpty()) stack.pop();

        }

        return stack.isEmpty();

    }

}

24 views
0 replies
2 upvotes

Interview problems

check Valid Parenthesis C++ Easy Approch using Stack

#include<bits/stdc++.h>

bool isValidParenthesis(string s)

{

    int n = s.size();  

    stack<char> check;

 

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

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

 

            check.push(s[i]);

        }

        else{

            if(check.empty()){

                return false;

            }

 

            if (check.top() == '(' && s[i] == ')' ||

                check.top() == '{' && s[i] == '}' ||

                check.top() == '[' && s[i] == ']'){

                    check.pop();

            }

            else{

                check.push(s[i]);

            }

        }

    }

 

    if(check.empty()){

        return true;

    }

    else{

        return false;

    }

}

100daysofcode

48 views
0 replies
1 upvote
Full screen
Console