What's going on, guys?
Andy here.
And in this video, we're going to do something special.
We will solve a hard interview question from lead code, which is commonly asked a top companies like
Amazon, Bloomberg, Facebook and Google.
And it is called Borst Balloons.
Now, this challenge is going to use a special dynamic programming approach, which I'm sure you really
love.
It is called the mix dynamic programming.
So stick with me until the end of the video and make sure you check out our giveaway, because I will
have a one on one Skype session with one likely winner.
So all you have to do is going to be at the end of the video.
See you there.
And let's solve the problem.
We've seen my last night they froze.
No cameras was no posts just like that one time at Chelo.
Good thing, ma'am, we're pulling our phones.
Bullets giver and index from zero to a minus one.
Each balloon is painted with a number on it, represented by a ray mouse.
You are asked to burst all the balloons if you burst the balloon.
I.
That's a typo right there.
You will get numbers left.
Cross the numbers.
I crossed names.
Right.
Coins here left the right or the agent iness of I.
Right.
So initially the idea sentences of our minus one and plus one.
But after rebirths some balloons, they would be different than that after the birth.
The left and right then becomes obvious and naturally find the maximum coins you can collect by bursting
the balloons wisely.
You may imagine numbers of minus one equals names of N equals one.
Right.
So if we bought the first balloon, obviously we won't have a left balloon.
Right.
So we are going to obtain nums one cross nums.
Right.
That's why numbers minus one is one.
So analysts are equal than 500 names of Ireland, what we call them 100.
That's perfect.
And you might need some time.
I recommend you post this video and go for the input.
Free one five eight.
And explain yourself why the output is one hundred sixty seven.
Right.
Because we are going now straight into the solution.
All right, guys, we start by identifying what kind of problem is this?
And this is an optimization problem because it asks you to find the minimum or the maximum cost of doing
something.
And they define the cost in their own way.
So this kind of problems, the optimization problems are solved in two possible manners greedily or
by dynamic programming approach.
And I recommended to post the video now and think about some greedy approach.
All right.
If you can't afford enough of it, you've probably noticed that there is no suitable greedy approach
here.
And one more here that is going to tell you that is the size of end, right?
Because when we usually solve problems greedily, we just saw the input in some way and then it worked
smoothly.
So the time complexity is bigger, Wolf.
And again, so N would have been greater than 500, something like, let's say one hundred thousand.
Right.
But because N is 500, we are going to have a solution here in Bago of N Cube and it's going to be a
dynamic programming Y.
And if you even have solved some problems similar if this one, you will notice furthermore that this
is a mixed dynamic programming approach.
But if you haven't, that's totally cool.
We will find out right now what this means.
Now, when we usually solve dynamic programming problems, we break the bigger problem into smaller
ones, solve those problems and then combine them together to get the answer for the bigger one here,
because this is a mixed dynamic programming problem.
The bigger problem is the whole range of balloons and the smaller problems are lethal ranges of balloons.
So our DP is going to sound like this.
BP of left and right is going to be the maximum points you get for bursting, right?
All the balloons from the left one to the right one.
Right.
So let's comment this.
And this is our DP.
Right.
So we want to burst all the bodies from the position left to the position right.
We vote caring about bursting all the other balloons and getting maximum points for that.
Perfect.
Now, if we manage to compute this dynamic programming, we know that our answer is going to be DP of
one.
And now we have to think about the recurrence relation.
And 99 percent of the times for this kind of problems, the recurrence relation consists of another
for loop in which we fix an intermediate point for computing our DEPI of left and right.
We will need to fix some intermediate position.
And let's call this B, right.
We will fix some B between left and right.
And we have to give this B some meaning.
And our meaning here is going to be B is the last balloon that we are going to burst in the range from
the left to the right.
Right.
So the last balloon to burst.
Now, do we know what is the answer for DEPI of left or right?
Knowing the P and we definitely do.
Because B is the last balloon we are going to burst.
So before bursting P, we are bursting all the balloons from position left, position B minus one bursting.
All the balloons from position P plus one.
The position right now we don't necessarily know the exact order in which we burst these balloons.
Right.
We can first burst the balloon.
Right.
Then what is the one who left then burst the balloon.
Minus three left, plus free and so on, but all we know for sure is that these two sub problems left
B minus one.
And people are still right, are independent of each other.
So DEPI of left and Right is going to be equal to DEPI of left and B minus one, plus DEPI of B plus
one.
And right.
Plus, the final cost, which is the number of coins that we get for bursting the people.
And what is that?
Do we know what is this?
And we surely do, because it is going to be numbers of people crossed.
What is going to be the balloon on the left of this PPIF balloon is going to be now left minus one.
Right.
Because we've burst all the balloons from left to right.
But B.
So we remain here if the balloon left minus one, which is intact and the balloon right, plus one which
is intact too.
Right.
So it's going to be months of left, minus one crossed NOM's of right, plus one.
And this is the course.
That's for some P.
This is the cost of bursting all the balloons from left to right.
And B, being the last balloon burst, we are going to fix all this possible piece from left to right.
And take that is against the maximum between all these expressions.
And this is going to be our DPL of left and right.
In the end, we return DEPI of one and end.
And our problem is solved.
What is that complexity?
Biegel of and Cube.
Because we have two nested for loops for the left and the right.
And for computing this DEPI state, we have another for loop for the.
Bingo.
Thank you guys.
Now it's time rather code for it.
We initially have this vector of integer knobs.
Now let's I don't want to worry about positions minus one or n I will build myself another vector which
will consist of very one in the beginning.
All these values from the vector nums and very one in the end.
So first of all, let's take the number of balloons, which is N equals nums, not size.
And after knowing this.
Remember the corner case.
If this is equal to zero, let's return zero.
Just to be safe about it.
And let's build our vector now.
So vector of integers.
Let's call it balloons.
Right.
So the short four balloons and initially it's going to have one value equal to one.
Then I will take each value in the vector of numbers.
So int num in nums.
And I will have balloons that push back of num.
Right.
And after that, in the end I will have again another one.
So balloons that push back of one.
Perfect.
Now I need to define my DEPI vector.
So I will have a vector of vector right.
Of integers which is going to be called DEPI.
And it will consist of.
And plus one vector of integers.
Right.
Of size and password.
And let's say they are all initially equal to zero.
So this is how you construct a two dimensional vector in the SDL library.
And let's think a little bit about the order in which we will compute our DP.
When we are going to find the value for DP of left and right, we are going to need the various for
some DEPI of a greater left.
Or maybe the same left, but smaller right.
So the right order in which we should compute is values.
We with the left starting that position.
And this time.
And as long as is greater or equal than one left minus minus for this left, I will have another for
loop for the right.
And the right obviously will start now from the left position.
As long as it is less or equal than N and the right bus pass.
And now I have two possible cases.
The first one I like to be safe about these kind of cases is when left is equal to the right.
So let's take it separately.
If left is equal right.
What is going to be my DP of left?
And right is going to be I would just burst the left balloon.
So this is balloons of left minus one crossed balloons of left crossed, balloons of left, plus one
as simple as that.
Now, if those two are different, we are going to have here free possible cases.
The first one is when be our balloon that we said we are going to burst.
The last is equal to the left right.
So P equals left.
We want to burst the left balloon.
The last one.
Right.
So for this DEPI of left and right, we can initialise this too.
Well, DEPI of Left Botswanan.
Right.
Because we will first burst those balloons.
Plus, when bursting the left balloon, we will have balloons of left minus one.
Crust balloons, balloons of left cross balloons of right plus one.
Perfect.
Now the second one is when P is going to be equal to the right.
So P equals, right.
Very similar to this one.
But in this case, we will have DEPI of left and right is equal to the maximum between the above value.
So what we already have here in DEPI of left and right.
And we will burst the right balloon the last right.
So DEPI of left and right, minus one plus when bursting that balloon.
I will have balloons of left minus one crossed balloons of right.
So right.
Crossed balloons of right.
Paswan.
Right.
And this is the second case now for the first case we will have left less than B, which is less than
right.
So here we will need A for loop.
Right.
So we will go with B from left plus one left plus one.
As long as he is less than right and people sparse.
And what is the formula for DEPI of left and right?
Well Dipu of Left-to-right is again going to be the maximum between what it is already here.
So DEPI of left and right.
And what is the value for this.
Is going to be DEPI of left and B minus one plus DPL B plus one.
And right again we don't know the specific order.
But we don't care.
They are independent.
Plus when bursting the people we will have bottles of B crust.
Balloons of F minus one crust.
Balloons.
Of right.
Plus one.
Right.
And this is it.
Not Indian.
When we will finish to execute these two nested for loops, we shall know the answer.
So we shall return DEPI of one and.
And let's see if this works.
That's from the code for it.
Fingers crossed.
All right.
Looks like it works.
Let's go for it.
Fingers crossed.
Let's see how we do.
And it is a success.
First up, then, 58 percent.
It's pretty good.
You can optimize this court in a lot of ways.
But for now, this is all lies.
All right, guys, we have sort of the burst balloons technical interview question super often asked
at firms like Amazon, Google and Facebook.
And now for my special giveaway, I am going to have a one on one call on Skype, on whatever topic
that you like.
And you can be the likely winner.
You just have to write in the comments your favorite dynamic programming problem or lead code and share
this video on Facebook.
I would randomly choose you and we will have that Skype call on whatever it's on our mind or whatever
your topic that you have to improve on.
All right, guys.
Now, as always, if you find this content valuable, make sure to support the channel.
So hit that like button the subscribe button.
And I can do this next time, like, never touch him.
And it's a good thing you get right.
I can't name a rapper that I trust.
I dream about many suits and it does.