1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Complexity Analysis
4.
4.1.
What is the most optimized approach to solving this problem?
4.2.
What if there is no balloon on any of the sides of the balloon which we want to burst?
4.3.
What is the time complexity for the most optimized approach?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Burst Baloon

Nishant Rana
1 upvote

## Introduction

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.

## Problem Statement

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 need to find the maximum number of coins we are left with after bursting all the balloons.

Let us see a few examples

Input 1: [1, 2, 3, 4, 5]

Output 1: 110

Explanation 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];

/*
the (i, j) pairs which have
a gap of 'g'.
*/
for(int g = 0; g < n; g++){

/*
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];
}

if(i - 1 >= 0) {
}

if(j + 1 < n) {
}

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).

Check out this problem - Frog Jump

### 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:

1. We discussed the Dynamic Programming approach to solve this question.
2. Then we discussed the time and space complexity to solve that question.

Refer to the most obliging blog on Dynamic programming for your future references→ Roadmap for Dynamic programming.

Check out more blogs on different Dynamic Programming problems like Longest Common Substring and Friends Pairing and Bursting Balloon Problem to read more about these topics in detail. And if you liked this blog, share it with your friends!

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 mock test 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.

Live masterclass