Burst Balloons ( google interview question )

Read the question from here: Burst Balloons

Let's solve this:

Suppose initially we have these 5 balloons.

Which balloons we can burst last?

we can burst any of the 5 balloons last, so there are five balloons to burst last.

Case 1: If we burst balloon 1 last.

Suppose we already know the maximum coins we can collect by bursting balloons from 2 to 5 let say M1.

So, now since 1 is the last balloon we are bursting so there are no balloons available in the left and right of the balloon 1. 

So, the total coin after bursting balloon 1 is:

Case 2: If we burst balloon 2 last.

Suppose we already know the maximum coins we can collect by bursting balloons from 1 to 1 let say M1 and from 3 to 5 is let say M2.

So, now since 2 is the last balloon we are bursting so there are no balloons available in the left and right of the balloon 2. 

So, the total coin after bursting balloon 2 is:

Case 3: If we burst balloon 3 last.

Suppose we already know the maximum coins we can collect by bursting balloons from 1 to 2 let say M1 and from 4 to 5 is let say M2.

So, now since 3 is the last balloon we are bursting so there are no balloons available in the left and right of the balloon 3. 

So, the total coin after bursting balloon 3 is:

Case 4: If we burst balloon 4 last.

Suppose we already know the maximum coins we can collect by bursting balloons from 1 to 3 let say M1 and from 5 to 5 is let say M2.

So, now since 4 is the last balloon we are bursting so there are no balloons available in the left and right of the balloon 4. 

So, the total coin after bursting balloon 4 is:

Case 5: If we burst balloon 5 last.

Suppose we already know the maximum coins we can collect by bursting balloons from 1 to 4 let say M1.

So, now since 5 is the last balloon we are bursting so there are no balloons available in the left and right of the balloon 5. 

So, the total coin after bursting balloon 5 is:

Final answer = Max( case1, case2, case3, case4, case5 )

Let suppose case2 will give us the maximum coins.

This is the situation of case2 in which we pick balloon 2 as the last balloon to burst.

Here we assumed that we already know the values of M1  and M2.

So, now let's find the value of M1 first.

Which balloons we can burst last, from balloon 1 to 1?

we can burst balloon1 last, as there is only one balloon to burst.

since balloon1 will burst last it means there is no balloon on the left of it so assume it as 1 and balloon2 will be on the right of it as balloon 2 will burst last from all the 1 to 5 balloons.

So the value of M1 is:

Now let's find the value of M2.

Which balloons we can burst last, from balloon 3 to 5?

we can burst any of the 3 balloons from 3, 4 and 5 last, so there are 3 balloons to burst last.

Case2.1: If we burst balloon 3 last from balloon 3 to 5.

Suppose we already know the maximum coins we can collect by bursting balloons from 4 to 5 let say M3.

So, now since 3 is the last balloon from balloon 3 to 5 that we are bursting so there are no balloons available on the right of the balloon3 so let assume it as 1 but the balloon 2 will be on the left of it as balloon2 will burst last from all the 1 to 5 balloons.

Means balloon 3 will be the second last balloon that we are bursting from all the balloon in this case.

So, the value of M2 in this case is: 

Case2.2: If we burst balloon4 last from balloon 3 to 5.

Suppose we already know the maximum coins we can collect by bursting balloons from 3 to 3 let say M3 and from 5 to 5 let say M4.

So, now since 4 is the last balloon from balloon 3 to 5 that we are bursting so there are no balloons available on the right of the balloon4 as all the balloons from 5 to 5 are already burst so let assume it as 1 but the balloon2 will be on the left of it as balloon2 will burst last from all the 1 to 5 balloons.

Means balloon4 will be the second last balloon that we are bursting from all the balloon in this case.

So, the value of M2 in this case is: 

Case2.3: If we burst balloon5 last from balloon 3 to 5.

Suppose we already know the maximum coins we can collect by bursting balloons from 3 to 4 let say M3.

So, now since 5 is the last balloon from balloon 3 to 5 that we are bursting so there are no balloons available on the right of the balloon5 as there is no balloon in the right so let assume it as 1 but the balloon2 will be on the left of it as balloon2 will burst last from all the 1 to 5 balloons.

Means balloon5 will be the second last balloon that we are bursting from all the balloon in this case.

So, the value of M2 in this case is: 

Now the Maximum answer in this case2 is: 

Now, let suppose Case2.2 will give us the maximum coins.

This is the situation of case2.2 in which we pick balloon 4 as the second last balloon to burst.

Here we assumed that we already know the values of M3 and M4.

So, now let's find the value of M3 first.

Which balloons we can burst last, from balloon 3 to 3?

we can burst balloon3 last, as there is only one balloon to burst.

Balloon on the left of it is balloon2 and right of it is balloon4 as in this case we are bursting only balloons from 3 to 3 and all the remaining balloons are alive.

It means balloon3 is the third last balloon that we are bursting.

So the value of M3 in this case is:

Now let's find the value of M4.

Which balloons we can burst last, from balloon 5 to 5?

we can burst balloon5 last, as there is only one balloon to burst.

Balloon on the left of it is balloon4 and right of it is nothing so assume it as 1 as in this case we are bursting only balloons from 5 to 5 and all remaining balloons are alive.

It means balloon5 is the third last balloon that we are bursting.

So the value of M4 in this case is:

Now the maximum answer in this case2.2 is:

So the exact answer to this example is this :

from the above diagram, you can easily see that there is a recurrence relation coming out of it.

Let f(L, R) = Maximum coin we can get by bursting all the balloons from index L to R.

f(L, R) = Max( for all k from L to R:  f(L, k-1) + f(k+1, R) + Value[L-1] * Value[k] * Value[R+1] )

K: Which is the last balloon that we burst from L to R.

As K will be the last balloon from L to R to burst so the neighbor of K will be the balloon at index L-1 and at index R+1.

Base case: If ( L > R ) return 0.

Visit this link for source code: Source code

Hope reading it will worth you 🙃.