Last updated on July 20th, 2024 at 04:11 am

Here, We see Burst Balloons LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Divide and Conquer, Dynamic Programming

Companies

Google, Snapchat

Level of Question

Hard

Burst Balloons LeetCode Solution

Problem Statement

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:
Input: nums = [3,1,5,8]
Output: 167
Explanation: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

Example 2:
Input: nums = [1,5]
Output: 10

1. Burst Balloons LeetCode Solution C++

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size() + 2;        
        vector<vector<int>> dp(n, vector<int>(n));
        vector<int> new_nums(n, 1);
        int i = 1;
        for(auto num : nums) {
            new_nums[i++] = num;
        }
        for(int len = 2; len <= n; len++) { 
            for(int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                for(int k = i + 1; k < j; k++) { 
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + new_nums[i] * new_nums[k] * new_nums[j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

2. Burst Balloons LeetCode Solution Java

class Solution {
public int maxCoins(int[] nums) {
    int[] inums = new int[nums.length + 2];
    int n = 1;
    for (int x : nums) if (x > 0) inums[n++] = x;
    inums[0] = inums[n++] = 1;
    int[][] memo = new int[n][n];
    return burst(memo, inums, 0, n - 1);
}

public int burst(int[][] memo, int[] inums, int left, int right) {
    if (left + 1 == right) return 0;
    if (memo[left][right] > 0) return memo[left][right];
    int ans = 0;
    for (int i = left + 1; i < right; ++i)
        ans = Math.max(ans, inums[left] * inums[i] * inums[right] + burst(memo, inums, left, i) + burst(memo, inums, i, right));
    memo[left][right] = ans;
    return ans;
}
}

3. Burst Balloons Solution JavaScript

var maxCoins = function(nums) {
  var auxArray = new Array(nums.length+2).fill(null);
  let idx = 1;
  for (let numsVal of nums){
    if(numsVal > 0) auxArray[idx++] = numsVal;  
  } 
  auxArray[0] = auxArray[idx++] = 1;
  var cache = Array.from({length: idx}, ()=>new Array(idx).fill([]));
  return burst(cache, auxArray, 0, idx - 1);
}

function burst(cache, auxArray, left, right) {   
  if (left + 1 == right) return 0;
  if (cache[left][right] > 0) return cache[left][right];
  let max = 0;
  for (let idx = left + 1; idx < right; idx++)
      max = Math.max(max, auxArray[left] * auxArray[idx] * auxArray[right] + burst(cache, auxArray, left, idx) + burst(cache, auxArray, idx, right));
  cache[left][right] = max;
  return max;
}

4. Burst Balloons Solution Python

class Solution(object):
    def maxCoins(self, nums):
        nums = [1] + nums + [1]
        n = len(nums)
        dp = [[0] * n for _ in xrange(n)]
        def calculate(i, j):
            if dp[i][j] or j == i + 1: # in memory or gap < 2
                return dp[i][j]
            coins = 0
            for k in xrange(i+1, j): # find the last balloon
                coins = max(coins, nums[i] * nums[k] * nums[j] + calculate(i, k) + calculate(k, j))
            dp[i][j] = coins
            return coins
        return calculate(0, n-1)