Recently I have been using Feynman technique to learn things. So I thought , why not use medium to share what I learned. It will be just like a swiss knife. So , I will be solving the famous stack problem of balanced parentheses or valid parentheses.

This problem is quite popular among the big tech giants and is asked often.

Its also present in leetcode Here is the link:

https://leetcode.com/problems/valid-parentheses/

parentheses means that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested. Consider the following correctly balanced strings of parentheses:

These are the some of the following balanced parentheses :

(()()()())

(((())))

(()((())()))

And the unbalanced are:

((((((())

()))

The challenge then is to write an algorithm that will read a string of parentheses from left to right and decide whether the symbols are balanced. To solve this problem we need to make an important observation. As you process symbols from left to right, the most recent opening parenthesis must match the next closing symbol. Also, the first opening symbol processed may have to wait until the very last symbol for its match. Closing symbols match opening symbols in the reverse order of their appearance; they match from the inside out. This is a clue that stacks can be used to solve the problem.

So for achieving the solution to such a algorithm we need to decide the suitable data structure that has a time and space complexity as low as possible.

So my approach to the problem is as following:

.Traverse the string

1. ​If there is an opening bracket, push is onto the stack.
2. If there is a closing bracket, check the top of the stack.
3. If the top of the stack contains the opening bracket match of the current closing bracket, then pop and move ahead in the string.
4. If the top of the stack is not the opening bracket match of the current closing bracket, the parentheses are not balanced. In that case, break from the loop.
5. If the stack is empty, the parentheses are not balanced.

• After traversing, if the stack is not empty, then the parentheses are not balanced. Otherwise, print balanced.

The code for the following is as follows:

class Solution {
public:
bool isValid(string A) {
stack<char> s;

for(int i=0;i<A.size();i++){

if(A[i]==’(‘ || A[i]==’{‘ || A[i]==’[‘){
s.push(A[i]);
} else{

if(s.empty()) return false; /// imp otherwise run time erro
else if(A[i]==’)’){
if(s.top() == ‘(‘) s.pop();
else return false;
}else if(A[i]==’}’){
if(s.top() == ‘{‘) s.pop();
else return false;
}else if(A[i]==’]’){
if(!s.empty() && s.top() == ‘[‘) s.pop();
else return false;
}

}

}

if(s.empty()) return true;

return false;
}

The time complexity is: O(N)

The space complexity is: O(N)