Valid Parentheses

Easy
0/40
Average time to solve is 10m
profile
Contributed by
399 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
Full screen
Console