Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Complexity Analysis
4.
Frequently Asked Questions
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

Author Nishant Rana
1 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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??

Balloon Burst GIFs | Tenor

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.

Also Read About, Byte Array to String

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: 

illustration


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?

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

Check out this problem - Frog Jump

Frequently Asked Questions

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.

Keep Coding!
Previous article
Scramble String
Next article
Maximum Product of Two Non-intersecting Paths in a Tree
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass