312. Burst Balloons

Problem Description

You are presented with a hypothetical situation involving n balloons, each painted with a number. These balloons are indexed from 0 to n - 1 and the numbers painted on them are given in an array called nums. Your task is to "burst" all of these balloons in such a way that allows you to collect the maximum number of coins possible.

The main rule to remember is that when you burst a balloon at index i, you collect a number of coins equal to the product of the numbers on three balloons: the one at i, the one immediately before it (i - 1), and the one immediately after it (i + 1). If there is no balloon at i - 1 or i + 1 (which would be the case if i is at the start or end of the array), then you pretend there is a balloon with the number 1 painted on it.

The challenge is to find the sequence of bursting balloons that yields the highest total number of coins.

Intuition

To arrive at a solution for this problem, consider that the last balloon you burst would allow you to collect nums[0] * nums[i] * nums[n-1] coins, where i is the index of this last balloon. Since nums[0] and nums[n-1] would be out of bounds after bursting all other balloons, we treat them as 1.

This suggests a dynamic programming approach where we consider smaller subproblems and build up to the full solution. The intuition behind the provided solution is to transform the problem into considering the maximum coins that can be collected by bursting the balloons within a subinterval of the original array.

By iteratively expanding these intervals and calculating the maximum number of coins that can be collected when bursting the last balloon in these subintervals, we can use previously solved smaller intervals to help calculate larger intervals. This concept is similar to matrix chain multiplication, where optimal solutions to smaller subproblems can be used to construct the final solution.

The idea is to iteratively consider all possible subintervals and all possible last balloons to burst within each subinterval. By doing so, we use the dynamic programming (DP) array dp to store the maximum coins obtained for each subinterval, so that we do not have to re-calculate the coins for those intervals again. The process starts from the smallest intervals and works its way up to the interval covering the entire range.

In the implementation, the dp array is first initialized to store zero values. Then, for each subinterval length l, starting at 2 and going up to n, we calculate the maximum coins for starting subintervals at index i and ending at j, using all possible last balloons k to find the best option. The final answer is then taken from the dp entry that covers the entire range, excluding the artificial balloons at both ends (that only serve the purpose of simplifying boundary conditions).

Learn more about Dynamic Programming patterns.

Solution Approach

The solution approach involves dynamic programming, which is a method for solving complex problems by breaking them down into simpler subproblems. The solution uses a 2D array, often referred to as a "DP table", to store the maximum number of coins that can be collected by bursting balloons within a specific subinterval of the array.

Let's delve into how the solution is implemented:

We first add a 1 at the beginning and the end of the nums array. This step simplifies our calculations for cases when we burst the first or the last balloon in the original array.
We define n as the length of this new array, now including the two additional balloons with a 1 painted on them.
We initialize a 2D array called dp with dimensions n by n, setting all values to 0. dp[i][j] will store the maximum coins that can be collected by bursting all balloons between index i and j.
We iterate through all possible lengths of subintervals l, starting from 2. We choose 2 because a subinterval must contain at least one balloon to burst (situated between the two 1s we added).
For each subinterval length (l), we find the start (i) and end (j) of the subinterval. We restrict our subinterval to be within the bounds of the array.
For each subinterval from i to j, we consider each balloon k as the last balloon to burst in this subinterval. We calculate the coins collected from bursting balloon k last, which is nums[i] * nums[k] * nums[j], and add to it the coins collected from the subintervals [i, k] and [k, j] which we have already calculated and stored in our dp table previously.
We update dp[i][j] with the maximum number of coins found for bursting all balloons between i and j.

The nested loops in the code iterate over subintervals and the potential last balloons that could be burst in that interval. The innermost loop picks the best choice for the last balloon to maximize the coins collected.

Finally, the result is the value in dp[0][n-1], where n-1 is the index after the last artificial 1.

This solution effectively builds the solution from smaller intervals to larger ones and uses previously computed results for efficiency, avoiding redundant calculations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example with the following balloon numbers: nums = [3, 1, 5, 8]. Following the given solution approach:

We first add 1 at the beginning and the end to get [1, 3, 1, 5, 8, 1] to account for the boundaries.
The length n of the new array is 6.
We initialize a 6x6 DP table with zeros. This table will help us remember the best solutions for subproblems.
We consider subinterval lengths l starting from 2, because a subinterval should have at least one balloon.
For l = 2, we have subintervals [1,3], [2,4], [3,5], and [4,6]:
- For subinterval [1,3], the only balloon to burst is 3 (as 1 and 1 are our added boundaries), and it gives 1 * 3 * 1 = 3 coins.
- Similarly, for [2,4], bursting 1 would give 3 * 1 * 5 = 15 coins, and so on for the other subintervals.
Our DP table is updated for these subintervals.
With l = 3, we have subintervals [1,2,4], [2,3,5], and [3,4,6]:
- Take [1,2,4], if we decide to burst balloon 2 last, we get 1 * 1 * 5 + dp[1][2] + dp[2][4] = 5 + 3 + 15 = 23 coins. For [2,3,5], the last burst 3 gives 3 * 5 * 1 + dp[2][3] + dp[3][5] coins, and so on.
We update our DP table accordingly.
This process is continued, expanding the size of subintervals until l = n - 1, where n is the length of our new array, and our subinterval is the entire array.

For each subinterval at each l, we consider all possible balloons that could be burst last, calculate the coins we can collect, and choose the maximum among them to update our DP table.

The result would then be in dp[0][n-1] which in this case will store the maximum number of coins we can collect from [1, 3, 1, 5, 8, 1].

Walkthrough example with detailed subinterval analysis:

l=2:
- Subinterval [1,3] (burst 3): dp[1][3] = 1 * 3 * 1 + dp[1][2] + dp[3][3] = 3
- Subinterval [2,4] (burst 1): dp[2][4] = 3 * 1 * 5 + dp[2][2] + dp[4][4] = 15
- Subinterval [3,5] (burst 5): dp[3][5] = 1 * 5 * 8 + dp[3][4] + dp[5][5] = 40
- Subinterval [4,6] (burst 8): dp[4][6] = 5 * 8 * 1 + dp[4][5] + dp[6][6] = 40
l=3:
- Subinterval [1,2,4] (choose balloon 2 to burst last for max coins): dp[1][4] = max(calculate for bursting 2 last, calculate for bursting 3 last) = max(1*1*5+dp[1][2]+dp[3][4], 1*3*5+dp[1][3]+dp[4][4]) = max(23, 15+0+0) = 23
- Subinterval [2,3,5] (choose balloon 3 to burst last for max coins): dp[2][5] = max(calculate for bursting 3 last, calculate for bursting 4 last) = max(3*5*1+dp[2][3]+dp[4][5], 3*1*8+dp[2][4]+dp[5][5]) = max(40+15, 15+40+0) = 55
- Subinterval [3,4,6] (choose balloon 4 to burst last for max coins): dp[3][6] = max(calculate for bursting 4 last, calculate for bursting 5 last) = max(1*1*1+dp[3][4]+dp[5][6], 1*5*1+dp[3][5]+dp[6][6]) = max(1+0+0, 40+0+0) = 40

And continue this way until the entire array is covered, resulting in dp[1][5] for the maximum coins.

By the end of the dynamic programming process, we find that the maximum number of coins that can be earned by bursting all the balloons is dp[0][5].

Solution Implementation

1class Solution:
2    def maxCoins(self, nums):
3        """
4        Calculate the maximum coins that can be obtained by bursting the balloons wisely.
5
6        :param nums: A list of integer representing the number of balloons
7        :type nums: List[int]
8        :return: The maximum coins obtained
9        :rtype: int
10        """
11        # Add a balloon with value 1 to each end of the list to simplify calculations
12        nums = [1] + nums + [1]
13        # Calculate the length of the new nums list
14        n = len(nums)
15        # Initialize the dp (Dynamic Programming) table with zeros
16        dp = [[0] * n for _ in range(n)]
17
18        # Fill the dp table
19        # l represents the length of the range we're considering
20        for l in range(2, n):
21            # i represents the start of the range
22            for i in range(n - l):
23                # j represents the end of the range
24                j = i + l
25                # Test each possible position 'k' for the balloon to burst last in the range (i, j)
26                for k in range(i + 1, j):
27                    # Calculate the maximum coins by adding the coins obtained from bursting the current balloon
28                    # (nums[i]*nums[k]*nums[j]) plus the maximum coins from the two subranges (i, k) and (k, j)
29                    dp[i][j] = max(
30                        dp[i][j],  # Current max coins for range (i, j)
31                        dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]  # Max coins if balloon k is burst last
32                    )
33        # The maximum coins obtained will be in the top right corner of the dp table
34        return dp[0][-1]
35

1class Solution {
2
3    // Method to calculate the maximum coins after bursting all the balloons.
4    public int maxCoins(int[] nums) {
5        // Initialize an extended array that includes 1s at both ends.
6        int[] extendedNums = new int[nums.length + 2];
7        extendedNums[0] = 1;
8        extendedNums[extendedNums.length - 1] = 1;
9      
10        // Copy the original nums array into the extendedNums array, starting at index 1.
11        System.arraycopy(nums, 0, extendedNums, 1, nums.length);
12      
13        // Length of the extended array.
14        int n = extendedNums.length;
15      
16        // Create a DP table to store the results of subproblems.
17        int[][] dp = new int[n][n];
18      
19        // Iterate over all possible lengths (starting from 2 because we need at least
20        // one balloon between i and j to calculate coins).
21        for (int length = 2; length < n; ++length) {
22            // Iterate over the start index of the subarray.
23            for (int i = 0; i + length < n; ++i) {
24                // End index of the subarray.
25                int j = i + length;
26              
27                // Iterate over all possible last balloons to burst between i and j.
28                for (int k = i + 1; k < j; ++k) {
29                    // Update the DP table with the maximum coins from either the previously
30                    // computed number or the new number of coins obtained by bursting the
31                    // current balloon last, along with previously computed subresults.
32                    dp[i][j] = Math.max(dp[i][j],
33                            dp[i][k] + dp[k][j] + extendedNums[i] * extendedNums[k] * extendedNums[j]);
34                }
35            }
36        }
37      
38        // Final answer is the maximum coins we can get for the entire array,
39        // which is stored in dp[0][n - 1].
40        return dp[0][n - 1];
41    }
42}
43

1class Solution {
2public:
3    int maxCoins(vector<int>& nums) {
4        // Add 1 before the first and after the last element to handle edge cases
5        nums.insert(nums.begin(), 1);
6        nums.push_back(1);
7      
8        // Calculate the size of the modified vector
9        int n = nums.size();
10      
11        // Initialize a 2D DP array with 0s
12        vector<vector<int>> dp(n, vector<int>(n, 0));
13      
14        // Iterate over the balloons in windows of increasing size
15        for (int windowLength = 2; windowLength < n; ++windowLength) {
16            // i is the start index of the current window
17            for (int i = 0; i + windowLength < n; ++i) {
18                // j is the end index of the current window
19                int j = i + windowLength;
20                // k is the index of the last balloon to be burst in the current window
21                for (int k = i + 1; k < j; ++k) {
22                    // Update the DP table with the maximum coins obtained by bursting 
23                    // the last balloon at index k in the current window (subarray [i, j])
24                    // The equation considers the coins obtained from bursting balloons in
25                    // the subarrays [i, k] and [k, j], along with the coins from bursting
26                    // the k-th balloon with its adjacent balloons at indices i and j
27                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);
28                }
29            }
30        }
31      
32        // The optimal solution for the entire array is stored in dp[0][n - 1]
33        return dp[0][n - 1];
34    }
35};
36

1function maxCoins(nums: number[]): number {
2    // Obtain the length of the input array
3    let numberOfBalloons = nums.length;
4
5    // Initialize a 2D array `dp` (Dynamic Programming table) for memoization
6    // with dimensions (numberOfBalloons + 1) x (numberOfBalloons + 2),
7    // defaulting all cells to 0.
8    let dp = Array.from({ length: numberOfBalloons + 1 }, () => new Array(numberOfBalloons + 2).fill(0));
9
10    // Pad the array of nums with 1 on both ends to simplify edge cases.
11    nums.unshift(1);
12    nums.push(1);
13
14    // Reverse iterate over the array to calculate maximum coins using bottom-up approach,
15    // starting from the second to last element and going backwards.
16    for (let left = numberOfBalloons - 1; left >= 0; --left) {
17        for (let right = left + 2; right < numberOfBalloons + 2; ++right) {
18            // Check all possible balloons that can be burst between left and right
19            // excluding the boundaries, and compute the maximum coins that can be obtained.
20            for (let k = left + 1; k < right; ++k) {
21                // Calculate coins obtained by bursting k-th balloon between balloons at 'left' and 'right',
22                // and add the coins obtained from previously burst balloons on both sides.
23                let coins = nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right];
24                dp[left][right] = Math.max(coins, dp[left][right]); // Store the maximum in the DP table.
25            }
26        }
27    }
28    // Return the maximum coins obtained by bursting all balloons except the first and last added ones.
29    return dp[0][numberOfBalloons + 1];
30}
31

Time and Space Complexity

Time Complexity

The given code implements the dynamic programming approach to solve the burst balloons problem. The time complexity of the code is dependent on the nested loops used in the algorithm.

There is an outer loop that iterates through all possible lengths of the subarrays (denoted by l), which goes from 2 to n. So, it iterates n - 2 times.
For every possible length, there is a nested loop iterating over the start indices of the subarrays (denoted by i), and this runs for n - l iterations for each l.
Inside the second loop, there is an innermost loop that iterates through all possible k positions where the balloon can be burst, between the start and end of the subarrays (from i + 1 to j - 1 where j = i + l).

The combination of these nested loops looks something like a cubic number of operations, giving us a time complexity of O(n^3), where n is the number of balloons (including the two added ones).

Space Complexity

The space complexity is mainly dictated by the 2D dynamic programming array dp, which has a size of n * n.

As a result, the space complexity of the code is O(n^2), where n is the total number of elements in the augmented array nums.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don’t know