Burst Balloons

Problem

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.

Examples

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
Note: (1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. (2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Solution

Method 1 - Brute Force OR Backtracking

Intuition

The brute-force (backtracking) approach tries every possible order of bursting balloons. For each step, it chooses a balloon to burst, calculates the coins gained, and recursively solves the subproblem for the remaining balloons. Since the coins gained depend on the immediate neighbors, we must update the list after each burst. This explores all possible sequences, ensuring we find the maximum.

We have n balloons to burst, which mean we have n steps in the game. In the i th step we have n-i balloons to burst, i = 0~n-1.

Approach

• For each recursive call, iterate through the current list of balloons.
• For each balloon, calculate the coins as left * current * right, where left and right are the adjacent values (or 1 if out of bounds).
• Remove the chosen balloon and recursively compute the maximum coins for the remaining list.
• Track and return the maximum coins obtained across all choices.

Code

Java

public class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        List<Integer> balloons = new ArrayList<>();
        for (int num : nums) {
	        balloons.add(num);
	    }
        return backtrack(balloons);
    }

    private int backtrack(List<Integer> balloons) {
        if (balloons.size() == 1) {
	        return balloons.get(0);
	    }
        int max = 0;
        for (int i = 0; i < balloons.size(); i++) {
            int left = (i == 0) ? 1 : balloons.get(i - 1);
            int right = (i == balloons.size() - 1) ? 1 : balloons.get(i + 1);
            int coins = left * balloons.get(i) * right;
            List<Integer> next = new ArrayList<>(balloons);
            next.remove(i);
            max = Math.max(max, coins + backtrack(next));
        }
        return max;
    }
}

Python

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        def backtrack(balloons: list[int]) -> int:
            if not balloons:
                return 0
            max_coins = 0
            for i in range(len(balloons)):
                left = balloons[i - 1] if i > 0 else 1
                right = balloons[i + 1] if i < len(balloons) - 1 else 1
                coins = left * balloons[i] * right
                next_balloons = balloons[:i] + balloons[i+1:]
                max_coins = max(max_coins, coins + backtrack(next_balloons))
            return max_coins
        return

Complexity

• ⏰ Time complexity: O(n!)
• 🧺 Space complexity: O(n)

Method 2 - Another Naive approach, but towards DP

Intuition

The naive recursive approach explores every possible order of bursting balloons. For each step, it tries bursting each balloon, calculates the coins gained, and recursively solves the subproblem for the remaining balloons. Since the coins depend on the immediate neighbors, the list must be updated after each burst. This method guarantees the correct answer but is highly inefficient for large inputs.

Approach

• For each recursive call, iterate through the current list of balloons.
• For each balloon, calculate the coins as left * current * right, where left and right are the adjacent values (or 1 if out of bounds).
• Remove the chosen balloon and recursively compute the maximum coins for the remaining list.
• Return the maximum coins obtained across all choices.

Code

Java

public class Solution {
    public int maxCoins(int[] nums) {
        List<Integer> balloons = new ArrayList<>();
        for (int num : nums) {
	        balloons.add(num);
	    }
        return burst(balloons);
    }

    private int burst(List<Integer> balloons) {
        if (balloons.isEmpty()) {
	        return 0;
	    }
        int max = 0;
        for (int i = 0; i < balloons.size(); i++) {
            int left = (i == 0) ? 1 : balloons.get(i - 1);
            int right = (i == balloons.size() - 1) ? 1 : balloons.get(i + 1);
            int coins = left * balloons.get(i) * right;
            List<Integer> next = new ArrayList<>(balloons);
            next.remove(i);
            max = Math.max(max, coins + burst(next));
        }
        return max;
    }
}

Python

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        def burst(balloons: list[int]) -> int:
            if not balloons:
                return 0
            max_coins = 0
            for i in range(len(balloons)):
                left = balloons[i - 1] if i > 0 else 1
                right = balloons[i + 1] if i < len(balloons) - 1 else 1
                coins = left * balloons[i] * right
                next_balloons = balloons[:i] + balloons[i+1:]
                max_coins = max(max_coins, coins + burst(next_balloons))
            return max_coins
        return burst(nums)

Complexity

• ⏰ Time complexity: O(n!). Each recursive call branches into n subproblems, leading to factorial growth (but better than backtracking)
• 🧺 Space complexity: O(n). - The recursion stack can go as deep as n, and each call creates a new list of size up to n.

Method 3 - Top Down DP with Divide and Conquer

Intuition

Instead of bursting balloons in any order, we think in reverse: for any subarray, consider which balloon is the last to burst. Bursting the last balloon in a subarray splits the problem into two independent subproblems (left and right of the last balloon), making it suitable for divide and conquer with memoization.

Approach

• Add 1 to both ends of the array to handle boundaries.
• Define a recursive function burst(left, right) that returns the maximum coins for bursting all balloons between indices left and right (exclusive).
• For each possible last balloon i in (left, right), calculate coins as nums[left] * nums[i] * nums[right] + burst(left, i) + burst(i, right).
• Use a memoization table to store and reuse results for each (left, right) pair.
• The answer is burst(0, n-1).

Code

Java

public class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] updatedNums = new int[n + 2];
        int len = 1;
        for (int x : nums) }
	        updatedNums[len++] = x;
	    }
        updatedNums[0] = updatedNums[len++] = 1;

        int[][] memo = new int[len][len];
        return burst(updatedNums, memo, 0, len - 1);
    }

    private int burst(int[] nums, int[][] memo, 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, nums[left] * nums[i] * nums[right]
                + burst(nums, memo, left, i)
                + burst(nums, memo, i, right));
        }
        memo[left][right] = ans;
        return ans;
    }
}

Python

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        nums = [1] + nums + [1]
        n = len(nums)
        memo = [[0] * n for _ in range(n)]

        def burst(left: int, right: int) -> int:
            if left + 1 == right:
                return 0
            if memo[left][right]:
                return memo[left][right]
            ans = 0
            for i in range(left + 1, right):
                ans = max(ans, nums[left] * nums[i] * nums[right] +
                          burst(left, i) + burst(i, right))
            memo[left][right] = ans
            return ans

        return burst(0, n - 1)

Complexity

• ⏰ Time complexity: O(n^3). There are O(n^2) subproblems, and each subproblem does O(n) work.
• 🧺 Space complexity: O(n^2). - For the memoization table. Plus O(n) recursion stack depth.

Method 4 - Bottom-up DP

Intuition

Instead of solving the problem recursively, we use dynamic programming to build up solutions for smaller subarrays and use them to solve larger ones. By considering all possible last balloons to burst in each subarray, we can fill a DP table iteratively.

Approach

• Add 1 to both ends of the array to handle boundaries.
• Define dp[i][j] as the maximum coins obtainable by bursting all balloons between indices i and j (exclusive).
• For all subarray lengths from 2 up to n, and for all possible subarrays of that length:
  • For each possible last balloon k in (i, j), update dp[i][j] as the maximum of its current value and nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j].
• The answer is dp[0][n-1].

Code

Java

public class Solution {
    public int maxCoins(int[] nums) {
        int n = numslength;
        int[] updatedNums = new int[n + 2];
        int len = 1;
        for (int x : nums) {
	        updatedNums[len++] = x;
	    }
        updatedNums[0] = updatedNums[len++] = 1;

        int[][] dp = new int[len][len];
        for (int k = 2; k < len; ++k) {
            for (int left = 0; left < len - k; ++left) {
                int right = left + k;
                for (int i = left + 1; i < right; ++i) {
                    dp[left][right] = Math.max(
                        dp[left][right],
                        nums[left] * updatedNums[i] * updatedNums[right] + dp[left][i] + dp[i][right]
                    );
                }
            }
        }
        return dp[0][len - 1];
    }
}

Python

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        nums = [1] + nums + [1]
        n = len(nums)
        dp = [[0] * n for _ in range(n)]
        for k in range(2, n):
            for left in range(0, n - k):
                right = left + k
                for i in range(left + 1, right):
                    dp[left][right] = max(
                        dp[left][right],
                        nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]
                    )
        return dp[0][n - 1]

Complexity

• ⏰ Time complexity: O(n^3). - There are O(n^2) subproblems, and each subproblem does O(n) work.
• 🧺 Space complexity: O(n^2). For the DP table.