Last updated on January 14th, 2025 at 06:21 am

Here, we see a Burst Balloons LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Divide and Conquer, Dynamic Programming

Companies

Google, Snapchat

Level of Question

Hard

Burst Balloons LeetCode Solution

1. 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 i^th 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

2. Coding Pattern Used in Solution

The coding pattern used in this problem is “Dynamic Programming with Memoization”. The problem involves breaking down the task into smaller overlapping subproblems, solving each subproblem once, and storing the results to avoid redundant computations.

3. Code Implementation in Different Languages

3.1 Burst Balloons 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];
    }
};

3.2 Burst Balloons 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.3 Burst Balloons 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;
}

3.4 Burst Balloons 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)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n³)	O(n²)
Java	O(n³)	O(n²)
JavaScript	O(n³)	O(n²)
Python	O(n³)	O(n²)

The O(n³) time complexity arises from the three nested loops or recursive calls for all subarrays.
The O(n²) space complexity is due to the 2D DP table or memoization array.
The problem is a classic example of Dynamic Programming with Memoization, where overlapping subproblems are solved efficiently.