We are drinking standard jasmine tea today.

This episode we're going to be continuing with our lead coating practice.

This time, we're going to do it in Python just to switch things up a bit.

What I'm trying to do for you guys is cover as much ground as I can.

That way, next time you see a similar type of problem, it doesn't take you by surprise because there's only so many different algorithms out there.

You just need no, a few good standard ones.

I understand how to approach a number of problems, and that should get you well in your way.

So without further ado, let's get into it.

The first of these questions is your given the string of unbalanced parentheses, and you need to find the total number of parentheses that need to be added to balance this strength.

And this is a very typical problem.

I was actually just ask this in one of my recent interview loops, so you definitely want to know how to solve it.

Now there is a brute force technique for solving this where you go through a district character by character and for each character you scan the whole entire string and see if you can find a match and you know that's gonna be like big o of end square time and you're not gonna want do that.

The solution is going to be to use a stack, and as you go through the string, you push characters on the stack and then you pop them off.

When you find a right, Prentiss, see if you happen to get a right prentiss E.

But the top item on the stack is not a left Prentiss E.

Then you know that you have an unbalanced parent and you could just add one to your total count.

When you finish iterating throughout the characters, then you just count the total number of items in the stack.

That's the number of left parentheses that were never meshed.

There's going to be your answer.

The run time is going to be a single passed through the characters up to scream.

So that is in your time and the space complexity.

Well, that's going to be linear as well, because you could be India pushing everything onto the stack.

Every single character if every single character is a left parentheses, so that's going to be linear as well.

I remember when that was fresh out of college.

I would always get stumped on questions like these because my college course has never taught me about cues and stacks.

All right, moving on.

So we're going to keep clicking on the next one until we find another interesting problem and we're looking again for easy or medium problems.

Now I've actually order pre found a problem for you guys and solved as well.

And you have.

The purpose of this video isn't necessarily for me to show you what I'm doing.

As I'm solving these problems.

I just want to cover the solution for you because I think that's going to be the best use of your time.

So this question is given the string of words Reverse the words in the string.

If the emperor is the sky's blue, then the upper shifty blue is sky.

The I think reversing words in the string is a pretty good problem, actually, because there's many different ways to solve it and was going to be interesting.

Is Thea analysis?

Essentially, you can go through one pass and you have two variables.

The start of a ward and then the end of a ward.

And as you're going through, you look for a space.

When you find the space, you know that that's the end of a word.

So you go through, you collect other words together, you have an array of other words in the string that you straight through that array of words in reverse order.

Add those words together and you return that result.

That's going to be the words reversed and the runtime for this should be in your time with regards to the length of the input.

And then the space requirement here is going to be as well been near.

You know, if your method needs to return a string of words.

By definition, that method is going to require, at least in your space, just to return the output.

Anyway, we can take a look at the solution that put together here, which does with that, describe the first portion interests through the characters in the array and collects a bunch of awards.

And then there's the Edge case where I used to get that last word because the last word does not end in a space, Necessarily.

Then we reverse the words.

This reversal process will probably take linear time as well.

And this is somewhat inefficient.

I couldjust breakthrough towards in reverse order.

But you know, we're taking linear time anyways, so reversing this is just gonna be another than your past.

It's not going to actually change that linear time analysis.

Is that the big O of end?

It will be big o of to it.

Either way's still linear.

Then we joined the words That's when they had another past.

So this probably runs in, like, three end time or something like that.

We can run.

Some may see how fast it is gonna take faster than 20% 5000 submissions, which is fine.

Really, I I could try to make a little bit faster.

So what I did here was I removed the call to reverse the upwards and iterated through the words in backwards order that removed at least one past.

And it's a little bit faster.

It's my solutions faster than 34% of prep on solutions now.

Yeah, I saw some of the solutions out there.

The faster ones.

They're selling this in, like, one line of code or five lines of code.

And yeah, you can do that.

If you know all the built in functions for python, I would recommend that if you're solving this for your own benefit, don't just resort to using those built in functions you know, functions like Split, which will automatically split a string based on the spaces, and they'll do it using C routine.

Such that is really fast.

It's going to be better for you to go through this, assuming you didn't have so many built ins such that you can really understand that time space complexity analysis for this.

Anyway, let's move on to the third problem I have prepared for you guys here.

The 3rd 1 is on daily temperatures.

The way this one works is they give you an array where you have temperatures for each day, and you need to find how many days you need to wait to the next warmest temperature for each day and you returned in the race.

You know, you may say you have to wait one day, one day, four days, two days, one day when they and if the temperature never gets warmer than that current day, then you need to return zero.

This problem I don't like so much because Number one is kind of a difficult set up.

You know, it takes some time to even understand what they're trying to ask for.

The other issue, I think, is that it's kind of a gotcha problem.

This one.

You either get disillusion or you don't probably the brute force approach, which it's good to mention if you can figure it out.

Sometimes the brute force approach is a little difficult to even figure out what they want.

And, you know, it's like it takes quadratic time as loop it more difficult to calculate that out.

But this one is relatively simple.

You just go through an end square time because for each element in the array, you have to reiterate through the rest of the items in the array to figure out what's the next highest element is gonna be n squared time.

Yeah, sure, that works, and in fact is not best solution if you're really limited on space, for whatever reason, however, most of the time people are going to want a faster time algorithm.

I believe I was actually asked this question before to one time.

It sounds very familiar to me.

And you know, the way you can solve this again is using stacks and stacks are something you've gotten, though, because they're just used all over the place.

Anytime there's something tricky, some tricky algorithm or something, you probably need a steak or a hash map or a cute, and so the key that this is you go through each temperature and you push them onto a stack.

Whenever a new temperature comes in, you check the O temperatures in the stack.

And if that temperature is greater than any other temperature in this, like then you know that you've got a warmer day.

You can calculate the difference and index the difference in days between that new temperature and the temperature that was previously in the stack.

And then you can just put that out, put into some output that right, and you can imagine that you go through this for each element in the array, and you may be thinking what that still quadratic time, isn't it because you're going through each element India rate, that's and elements and that you could be checking a stack that's up to N elements as well, so that's still and square.

The trick here is to realize that you only need to check the top element in the stack.

If there was anything else that was higher temperature before that in the stack, it would have already been popped off and processed.

That's what makes this algorithm actually linear time, because for each element, you only check the top element in the stack.

Your total run time, then is going to be one passed through every temperature and then pushing and popping.

The temperature's at least once, so it's gonna be like to end or three in time or something like that Is linear time Indian.

Very tricky Little problem.

Funny to think about.

I would be surprised if anyone ever asked you this type of theme, but somebody did asked me this before.

In one problem I remember, and I think I got it, too.

If I were to run the solution, you will see that it's OK.

It's coming in at 20% faster than other solutions.

You know, I'm sure a lot of these other solutions are probably using built in functions and things like that just to get their programs to run faster.

It's probably not even in your time.

But if you're using built ins, then you could get your solution to probably run very quickly without even understanding that the big O time and illnesses may not even be as fast as what this is doing.

Okay, we got another problem here for you, the 4th 1 And unfortunately, a lot of these problems that we've had today haven't been really good problems.

I think like they're tricky.

A lot of you seem to be pretty tricky.

It's not my favorite, this one.

There's another pretty tricky one, which I didn't really enjoy.

Solving it is sub a raise some.

So even the set up of the problem is a little bit difficult to understand.

But they want to say that, given an interview, okay, find the total number of continuous supper Reyes who some equals that interject.

Yeah, I thought about this problem for a while and really want the best solutions I could think of was brute force Quadratic solution.

It's a four loop inside the four where you have a starting position and the ending position, and you essentially calculate every single permutation.

And as you're doing this, you add up the sun and you can find out if that some ever equals this inter jure que if it does, you increment the count.

And, yeah, I can run this and get time limit exceeded.

The funny thing about this one is there is this totally bizarre solution, which you can solve in in your time.

So the trick to this one is you create a hash map of cumulative sums, which are sums that you can create from the first number.

And this hash map is the frequency of these.

So you go there, the elements in the array, you add up the numbers as you go through.

If the number is equal to K, then that's one count.

That's one match.

What you do is then you look into the hash map and you find if there's any other numbers, which is equal to some minus K, and if there are, then you add those to your come as well, because those could represent potential star points for you're a suburb.

Great.

Anyway, it's a pretty tricky question.

I wouldn't necessarily duo on this one too long.

Let's move on to the last one that we've got here.

The last one, unfortunately, is a little bit funner.

If this palindrome link list you're given that link lists and you need to figure out if that link list is a palindrome, it's I've gone ahead.

I've solved this for you and it's fairly simple, right?

Like you can go through the link list.

You push that limits onto a stack.

That's your first pass.

Then you've got this array.

You could just go through the array and just check that the first and last elements are the same than the second and second thing, last element under same and so forth, and that's a to pass over them, then your time, then your space.

Now it becomes interesting when you think about how can you do this without that space requirement?

I can't do it and say constant space, and there's this clever algorithm that you can do.

It's again one of these tricky things, but what you do is you can have two pointers and you can advance one pointer at twice as fast as the first pointer.

By doing so you can figure out what is the midpoint of this length list, right?

When the second point our guests at the end, the first pointer will only have been halfway through that list.

Then, from that point on, you take that first pointer and you take it to the end of the link list.

But as you go through, you reverse each link list.

Then what you have at the end is you have two pointers, the orginal pointers at the start and they have a second point at the end of the link list.

And then you can traverse bother them towards the middle, checking that the values are the same and that's how you can determine their palindrome.

It is also in your time, but it will require no space, which is pretty fun.

Actually, I thought that was pretty neat.

So I've got the algorithm for you hear the first portion Traverse is one pointer at normal speed, the second at double speed.

Then what they would do is they were reverse pointers and traverse the first point, which is only 1/2 way to the end of the link list.

And then the last portion is you've got one pointer at the head, one that the tail and just traverse them in words and you compare their values.

If they don't match up, it's false.

If they do match up, the answer's gonna be true.

I can run the solution and I can see that it's faster than 36% solutions, which seems good enough.