Burst Balloons

January 10, 2025

Burst Balloons : An In-Depth Explanation

The “Burst Balloons” problem challenges you to maximize the coins collected by strategically bursting balloons in a given array. Each balloon has a value, and bursting it earns coins equal to the product of its value and the values of its adjacent balloons.

If a neighboring index is out of bounds, it is treated as 1. The goal is to determine the optimal order to burst all balloons and achieve the maximum total coins.

Problem:

You are provided with an array of integers, nums, of size n. Each element nums[i] represents a balloon with a certain integer value. Your task is to burst all the balloons.

When you burst the i-th balloon, you earn coins equal to nums[i - 1] * nums[i] * nums[i + 1]. If i - 1 or i + 1 goes beyond the boundaries of the array, consider the out-of-bounds value as 1.

Your goal is to determine the maximum coins you can collect by strategically bursting all the balloons.

Problem Breakdown

Input: An array nums where each element represents a balloon’s value.
Bursting Rule: Bursting the i-th balloon gives coins equal to nums[i-1] * nums[i] * nums[i+1]. Treat out-of-bounds values as 1.
Goal: Find the maximum coins you can collect by bursting all balloons in the best order.
Challenge: The order of bursting affects the total coins, making it a combinatorial problem.
Approach: Use dynamic programming to calculate the maximum coins for subarrays and build up to the full solution.

Example 1

Input: nums = [4,2,3,7]

Output: 167

Explanation:

nums = [4,2,3,7] --> [4,3,7] --> [4,7] --> [7] --> []

coins = 4*2*3 + 4*3*7 + 1*4*7 + 1*7*1 = 143

Constraints:

n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100

Approach

Here’s the short approach without the formula:
1. Add Boundary Balloons: Add two virtual balloons with value 1 at the start and end of the array.
2. DP Table Setup: Create a 2D DP table dp[i][j] to store the maximum coins collectable from bursting balloons in the subarray nums[i] to nums[j].
3. Recursive Calculation: For each subarray [i, j], determine the best balloon k to burst last. The maximum coins for the subarray will depend on the maximum coins for the left and right subarrays and the coins from bursting balloon k.
4. Iterate Over Subarrays: Fill the DP table by considering all possible subarrays and lengths.
5. Return Result: The maximum coins are in dp[0][n-1], where n is the length of the modified nums.

There are mainly three approach to solve this problem –

Brute Force
Dynamic Programming (Top-Down)
Dynamic Programming (Bottom-up)

1. Brute Force (Recursion)

Time complexity:
Space complexity:

Python

C++

Java

JavaScript

Python

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]

        def dfs(nums):
            if len(nums) == 2:
                return 0

            maxCoins = 0
            for i in range(1, len(nums) - 1):
                coins = nums[i - 1] * nums[i] * nums[i + 1]
                coins += dfs(nums[:i] + nums[i + 1:])
                maxCoins = max(maxCoins, coins)
            return maxCoins

        return dfs(nums)

C++

class Solution {
public:
    int maxCoins(vector& nums) {
        nums.insert(nums.begin(), 1);
        nums.push_back(1);

        return dfs(nums);
    }

    int dfs(vector& nums) {
        if (nums.size() == 2) return 0;

        int maxCoins = 0;
        for (int i = 1; i < nums.size() - 1; i++) {
            int coins = nums[i - 1] * nums[i] * nums[i + 1];
            vector newNums = nums;
            newNums.erase(newNums.begin() + i);
            coins += dfs(newNums);
            maxCoins = max(maxCoins, coins);
        }
        return maxCoins;
    }
};

Java

public class Solution {
    public int maxCoins(int[] nums) {
        int[] newNums = new int[nums.length + 2];
        newNums[0] = newNums[nums.length + 1] = 1;
        for (int i = 0; i < nums.length; i++) {
            newNums[i + 1] = nums[i];
        }

        return dfs(newNums);
    }

    public int dfs(int[] nums) {
        if (nums.length == 2) {
            return 0;
        }

        int maxCoins = 0;
        for (int i = 1; i < nums.length - 1; i++) {
            int coins = nums[i - 1] * nums[i] * nums[i + 1];
            int[] newNums = new int[nums.length - 1];
            for (int j = 0, k = 0; j < nums.length; j++) {
                if (j != i) {
                    newNums[k++] = nums[j];
                }
            }
            coins += dfs(newNums);
            maxCoins = Math.max(maxCoins, coins);
        }
        return maxCoins;
    }
}

JavaScript

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    maxCoins(nums) {
        nums.unshift(1);
        nums.push(1);
        return this.dfs(nums);
    }

    /**
     * @param {number[]} nums
     * @return {number}
     */
    dfs(nums) {
        if (nums.length === 2) return 0;

        let maxCoins = 0;
        for (let i = 1; i < nums.length - 1; i++) {
            let coins = nums[i - 1] * nums[i] * nums[i + 1];
            let newNums = nums.slice(0, i).concat(nums.slice(i + 1));
            coins += this.dfs(newNums);
            maxCoins = Math.max(maxCoins, coins);
        }
        return maxCoins;
    }
}

2. Dynamic Programming (Top-Down)

Time & Space Complexity

Time complexity:
Space complexity:

Python

Java

C++

JavaScript

Python

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        dp = {}
        def dfs(l, r):
            if l > r:
                return 0
            if (l, r) in dp:
                return dp[(l, r)]

            dp[(l, r)] = 0
            for i in range(l, r + 1):
                coins = nums[l - 1] * nums[i] * nums[r + 1]
                coins += dfs(l, i - 1) + dfs(i + 1, r)
                dp[(l, r)] = max(dp[(l, r)], coins)
            return dp[(l, r)]

        return dfs(1, len(nums) - 2)

Java

public class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] newNums = new int[n + 2];
        newNums[0] = newNums[n + 1] = 1;
        for (int i = 0; i < n; i++) {
            newNums[i + 1] = nums[i];
        }

        int[][] dp = new int[n + 2][n + 2];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -1;
            }
        }

        return dfs(newNums, 1, newNums.length - 2, dp);
    }

    public int dfs(int[] nums, int l, int r, int[][] dp) {
        if (l > r) {
            return 0;
        }
        if (dp[l][r] != -1) {
            return dp[l][r];
        }

        dp[l][r] = 0;
        for (int i = l; i <= r; i++) {
            int coins = nums[l - 1] * nums[i] * nums[r + 1];
            coins += dfs(nums, l, i - 1, dp) + dfs(nums, i + 1, r, dp);
            dp[l][r] = Math.max(dp[l][r], coins);
        }
        return dp[l][r];
    }
}

C++

class Solution {
public:
    int maxCoins(vector& nums) {
        int n = nums.size();
        vector newNums(n + 2, 1);
        for (int i = 0; i < n; i++) {
            newNums[i + 1] = nums[i];
        }

        vector> dp(n + 2, vector(n + 2, -1));
        return dfs(newNums, 1, newNums.size() - 2, dp);
    }

    int dfs(vector& nums, int l, int r, vector>& dp) {
        if (l > r) return 0;
        if (dp[l][r] != -1) return dp[l][r];

        dp[l][r] = 0;
        for (int i = l; i <= r; i++) {
            int coins = nums[l - 1] * nums[i] * nums[r + 1];
            coins += dfs(nums, l, i - 1, dp) + dfs(nums, i + 1, r, dp);
            dp[l][r] = max(dp[l][r], coins);
        }
        return dp[l][r];
    }
};

JavaScript

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    maxCoins(nums) {
        let n = nums.length;
        let newNums = new Array(n + 2).fill(1);
        for (let i = 0; i < n; i++) {
            newNums[i + 1] = nums[i];
        }

        let dp = Array.from({ length: n + 2 }, () => new Array(n + 2).fill(-1));
        return this.dfs(newNums, 1, newNums.length - 2, dp);
    }

    /**
     * @param {number[]} nums
     * @param {number} l
     * @param {number} r
     * @param {number[][]} dp
     * @return {number}
     */
    dfs(nums, l, r, dp) {
        if (l > r) return 0;
        if (dp[l][r] !== -1) return dp[l][r];

        dp[l][r] = 0;
        for (let i = l; i <= r; i++) {
            let coins = nums[l - 1] * nums[i] * nums[r + 1];
            coins += this.dfs(nums, l, i - 1, dp) + this.dfs(nums, i + 1, r, dp);
            dp[l][r] = Math.max(dp[l][r], coins);
        }
        return dp[l][r];
    }
}

3. Dynamic Programming (Bottom-Up)

Time & Space Complexity

Time complexity:
Space complexity: $O(n^2)$

Python

Java

C++

JavaScript

Python

class Solution:
    def maxCoins(self, nums):
        n = len(nums)
        new_nums = [1] + nums + [1]

        dp = [[0] * (n + 2) for _ in range(n + 2)]
        for l in range(n, 0, -1):
            for r in range(l, n + 1):
                for i in range(l, r + 1):
                    coins = new_nums[l - 1] * new_nums[i] * new_nums[r + 1]
                    coins += dp[l][i - 1] + dp[i + 1][r]
                    dp[l][r] = max(dp[l][r], coins)

        return dp[1][n]

Java

public class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] newNums = new int[n + 2];
        newNums[0] = newNums[n + 1] = 1;
        for (int i = 0; i < n; i++) {
            newNums[i + 1] = nums[i];
        }

        int[][] dp = new int[n + 2][n + 2];
        for (int l = n; l >= 1; l--) {
            for (int r = l; r <= n; r++) {
                for (int i = l; i <= r; i++) {
                    int coins = newNums[l - 1] * newNums[i] * newNums[r + 1];
                    coins += dp[l][i - 1] + dp[i + 1][r];
                    dp[l][r] = Math.max(dp[l][r], coins);
                }
            }
        }

        return dp[1][n];
    }
}

C++

class Solution {
public:
    int maxCoins(vector& nums) {
        int n = nums.size();
        vector newNums(n + 2, 1);
        for (int i = 0; i < n; i++) {
            newNums[i + 1] = nums[i];
        }

        vector> dp(n + 2, vector(n + 2, 0));
        for (int l = n; l >= 1; l--) {
            for (int r = l; r <= n; r++) {
                for (int i = l; i <= r; i++) {
                    int coins = newNums[l - 1] * newNums[i] * newNums[r + 1];
                    coins += dp[l][i - 1] + dp[i + 1][r];
                    dp[l][r] = max(dp[l][r], coins);
                }
            }
        }

        return dp[1][n];
    }
};

JavaScript

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    maxCoins(nums) {
        let n = nums.length;
        let newNums = new Array(n + 2).fill(1);
        for (let i = 0; i < n; i++) {
            newNums[i + 1] = nums[i];
        }

        let dp = Array.from({ length: n + 2 }, () => new Array(n + 2).fill(0));
        for (let l = n; l >= 1; l--) {
            for (let r = l; r <= n; r++) {
                for (let i = l; i <= r; i++) {
                    let coins = newNums[l - 1] * newNums[i] * newNums[r + 1];
                    coins += dp[l][i - 1] + dp[i + 1][r];
                    dp[l][r] = Math.max(dp[l][r], coins);
                }
            }
        }

        return dp[1][n];
    }
}