Validate Parenthesis In a String (Coding interview problem) - Whiteboard Thursday

Check out the detailed data structures and algorithms course at www.interviewaccelerator.com
Today's problem is about validating parentheses. All good code editors need a way to tell you whether your code has the right set of parentheses. We will implement an algorithm that does just that.
Also look out for next week's problem that I mention in the video. Try it out yourself and subscribe to get notified when the solution comes out.

[@Bojl95]

just wanna thank you for all these videos man, they really help me out throughout this tough process

[@varungirdhar3840]

Exactly what I was looking for. Keep Going. Thanks allot for simplifying such problems!

[@tannerbarcelos6880]

I like this solution a lot. I knew I wanted to use a stack, but I was doing if statements of all the checks for closing matches and the code was really messy. The maps make the code super compact when doing the basic checks. Great work

[@locky2127]

We had this question on one of our tests for 1 point on my first semester of the first year of programming at university.

[@vinayakgupta1]

You make things look so easy!!! Great Job Please solve the hard questions of leetcode.......

[@MRTUnplugged]

amazing stuff mahn !! keep going :)

[@gopalrajpurohit879]

It is possible to perform stack operations on the given array itself, without changing input by three indices. In which case, we can do this in O(1) space complexity and O(n) time complexity. Also in case of single type of parenthesis only, it can simply be done with counter, where counter increments on left parenthesis and decrements on right parenthesis. Any time counter goes below zero.... we an return false. At the end counter need to be zero, else again return false.

[@ScutUrsula]

i was thinking exactly the same way :D

[@nipunkakshal3696]

I am not getting how the else if () is gonna return any boolean .. it will just return the value for the key provided .. any idea ?

[@rajeshkumar1149]

Hey great videos.a small suggestion ..it would be more helpful if you add a small explanation of why you chose that particular data structure for that problem and what performance benefits that particular ds has in terms of complexity

[@wulymammoth]

noprobs I think here it’s implied. He mentioned we wanted to know the “last” opening paren. With practice, we should intuitively be searching for some data structures that supports constant time lookup for last.

[@andreandrews6237]

so before watching this video, I'm thinking I'd do something like create a char dictionary (c#) of open parens as keys with the value being the closed parenthesis. From there it should be as simple as checking for the compliment (maybe using wrong term). Example (syntax could be off, but you should get it): bool valid = true; int opposite = str.Length - 1; dictionary dict = new dictionary(insert key,value pairs); for(int i = 0; i

[@Endede]

What does your solution return for "([]{})"?

[@ScutUrsula]

A simple approach is to use 3 integers (one for each type of parenthesis), initialize all integers to 0 and add +1 when you find an open parenthesis (only if the actual value of that integer is >= 0, otherwise you already had an open parenthesis of that type, so the string is already invalid) and subtract -1 when you find a closed parenthesis. At the end check all 3 integers to be 0 so that the sting is valid. If any of the integers is not 0, the sting is invalid.

[@wulymammoth]

Geronymo nice. This will being the space complexity down to O(1)

[@dragon9786]

Your solution won't work. If I have a string like ({[})] you will never have a negative integer during the loop and when the loop exits all values will be 0. However the string is not a valid combination of parentheses

[@wulymammoth]

Good catch, @dragon9786! @Geronymo, I guess this heuristic is invalidated, because it only checks that there are matching closing parens, but discounts the ordering in a problem where ordering does matter. When encountering a closing paren, like `)`, we need to ensure that the last opening paren was `(`, because something like `({)}` would bring the counts back to zero, but is invalid. If we know that we have only uniform opening parens and closing parens, then the algorithm would work.

[@ScutUrsula]

I see now, my mistake. My approach was not taking in account for that possibility indeed, so it is an invalid solution to this problem. It only works if the closing parentheses are the same type as the last opening ones

[@fawadhassan9036]

When are new videos coming

[@pratapdafedar7305]

@Irfan Baqui, How about this solution with space complexity = 1? parenthesis = 0; foreach(char ch in string) { switch(ch) { case '{': case '(': parenthesis ++; break; case '}': case ')': parenthesis --; break; } if(parenthesis < 0) { break; } //break from loop + optimisation. } if (parenthesis == 0) print("Equal"); else print("Not equal");

[@justmark8040]

The problem is not only to checking if the amount of opening parenthesis is equal to the amount of closing ones, you also have to check if they are correct. For example "( { ) }" should be incorrect, but your code says it's correct.

[@carlosmacias4230]

There is a bug in the code if a string starts with a closing parenthesis it would try to pop from an empty stack. I guess if the stack returns null in this case it wouldn't be a bug.

[@wulymammoth]

Carlos Macias this is what I was going to note, except he accounts for that by checking for the condition you’ve stated, but I believe that if the string starts with an opening paren, we could also exit early and return false

[@patilmeghesh91]

Y do we need a hash table or a dictionary, can v not use only a stack and a bunch of if else statements?

[@stewartzayat7526]

Theoretically, you could do everything with just ifs, that's how it was made after all, but you should also aim for readability of your code.

[@anibalasubramaniam4153]

Agreed, this is like parsing an expression except the only operator possible is concatenation.

[@deeppatel1654]

I did something like this //Stack To store last found parenthesis Stack open=new Stack(); //Hashmap to check if corresponding open parenthesis exist in stack HashMap close = new HashMap(); close.put('}', '{'); close.put(']', '['); close.put(')', ')'); //counter for number of parenthesis int count=0; //For loop to traverse the input String for(int i=0;i

[@vishal-sg1np]

Please write with dark colour sketch , your writing is not clear

[@ridhwaans]

In this problem, can you use a two pointers approach, to read parenthesis left and right? If it finds a pair, it will find the next pair with two pointers

[@aadhia9685]

Please use another colour sketch....please use low brightness... didnt understand wt ur writing....i have been following ur videos daily...

[@carpediemscrate1923]

am going to a lots of videos for this.. why u all not showing exact python program.. I didn't get this.. may be am the only dumb person here. I understand what will happen in algorithm. but I need program.. sorry man.. I just helpless!!

[@samarthtandon2163]

I also solve this problem using stacks.....