Again Coding Ninjas has come with a new challenge for you. Are you excited about the challenge? As the name suggests, Burst Balloon, what can be the problem? Any idea??
Source: Giphy
Don't you worry; with the help of the problem statement, it will be crystal clear in your mind how to deal with this data structure problem and what can be the best possible solutions to solve this.
You are given ‘N’ number of balloons numbered from 0 to N-1. You are given an array of ‘N’ integers. If you burst the ‘i’th balloon, you will get a[i - 1] * a[i] * a[i + 1] number of coins. If the index goes out of bounds, consider the array value for that index to be 1.
We will burst the balloons in the following order 4 -> 3 -> 2 -> 1 -> 5. We will get the coins 60 + 30 + 10 + 5 + 5 = 110 on each burst.
Input 2: [3, 10, 6]
Output 1: 204
Explanation 1: We will burst the balloons in the following order 10 -> 3 -> 6. We will get the coins 180 + 18 + 6 = 204 on each burst.
Recommended: Before watching out for the solution, why not try it by yourself?
Approach
We will solve this problem using Dynamic Programming. We will be making a DP table of size N * N (where ‘N’ is the number of array elements). We will store the answer for all (i, j) pairs, i.e., what is the maximum number of coins we can get if we burst all the balloons from ith balloon to the jth balloon.
DP[i][j] means the maximum coins we can get if we burst all the balloons from i to j.
We will first calculate the DP answer for bursting all the single balloons, i.e., (0, 0), (1, 1), (2, 2), etc.
Then we will calculate the DP answer for bursting the adjacent pairs, i.e., (0, 1), (1, 2), (2, 3), etc.
We will keep similarly calculating the DP values by increasing the length of bursting the adjacent balloons by 1.
In the end, we will just return the value of DP[1][N] because it will store the maximum coin we can generate if we burst all the balloons from 1 - N.
Refer to the below implementation of the above approach.
class Solution {
public int maxCoins(int[] a) {
int n = a.length;
//Initializing the DP table
int dp[][] = new int[n][n];
/*
Calculating the answer for all
the (i, j) pairs which have
a gap of 'g'.
*/
for(int g = 0; g < n; g++){
/*
Calculating the answer for
all the (i, j) pairs switch
a gap of 'g' between them.
*/
for(int i = 0, j = g; j < n; i++, j++){
/*
The inner for loop to find the
balloon which have to be burst
last to gain the maximum coins.
*/
for(int last = i; last <= j; last++){
int cans = 0;
//If last goes out of bounds
if(last - 1 >= i) {
cans = dp[i][last - 1];
}
//If last goes out of bounds
if(last + 1 <= j) {
cans += dp[last + 1][j];
}
int add = a[last];
if(i - 1 >= 0) {
add *= a[i - 1];
}
if(j + 1 < n) {
add *= a[j + 1];
}
dp[i][j] = Math.max(dp[i][j], cans + add);
}
}
}
return dp[0][n - 1];
}
}
Complexity Analysis
Time Complexity: The time complexity for the above approach is O(N ^ 3), where ‘N’ is the number of elements in the array. We are running three nested for loops, and each for loop will run ‘N’ times in the worst case.
Space Complexity: The space complexity for the above approach is O(N * N) (where N is the number of elements in the array) because we are maintaining a 2D D.P. table of size (N * N).
What is the most optimized approach to solving this problem?
The most optimized approach to solve this problem is using Dynamic Programming where we store the answer for all (i, j) pairs i.e, what is the maximum number of coins we can get if we burst all the balloons from ith balloon to the jth balloon.
What if there is no balloon on any of the sides of the balloon which we want to burst?
If there is no balloon on any of the sides of the balloon which we want to burst, then assume that there is a balloon of value 1 on the empty sides.
What is the time complexity for the most optimized approach?
The time complexity for the most optimized approach is O(N ^ 3), where ‘N’ is the number of elements in the array. We are running three nested for loops, and each for loop will run ‘N’ times in the worst case.
Conclusion
In this blog, we have covered the following things:
We discussed the Dynamic Programming approach to solve this question.
Then we discussed the time and space complexity to solve that question.
Suppose you want to learn more about Dynamic Programming and practice some questions that require you to take your basic knowledge of Dynamic Programming a notch higher. In that case, you can visit our Guided Path for Dynamic Programming. If you want to test your competency in coding, you may check out the mocktest series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Google, etc. In that case, you must look at the problems,interview experiences, and interview bundle for placement preparations.
Until then, All the best for your future endeavors, and Keep Coding.
39+ registered 