# Burst Balloons LeetCode Solution

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

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

## Burst Balloons LeetCode SolutionC++

``````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];
}
};```Code language: PHP (php)```

## Burst Balloons LeetCode SolutionJava

``````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;
}
}```Code language: PHP (php)```

## Burst Balloons SolutionJavaScript

``````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;
}```Code language: JavaScript (javascript)```

## Burst Balloons SolutionPython

``````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)```Code language: HTML, XML (xml)```
Scroll to Top