Burst Balloons

LeetCode 312: Burst Balloons Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses Interval Dynamic Programming to determine which balloon should be burst last within a specific range, allowing us to break the problem into independent subproblems.

You are given an array of numbers representing balloons. Bursting a balloon at index i yields coins equal to the product of the balloon's value and its immediate neighbors (nums[i-1] * nums[i] * nums[i+1]). When a balloon is burst, it is removed, and the remaining balloons become adjacent. The boundaries are treated as having a value of 1. The goal of the LeetCode 312 problem is to find the maximum number of coins collectible by choosing the optimal burst sequence.

Brute Force Approach for Burst Balloons

The naive approach involves trying every possible permutation of bursting the balloons. This is a classic backtracking strategy.

1. Choose any balloon i from the current set of n balloons.
2. Calculate the coins obtained: nums[i-1] * nums[i] * nums[i+1].
3. Remove balloon i from the array (shifting elements to close the gap).
4. Recursively solve for the remaining n-1 balloons.
5. Restore the balloon (backtrack) and try the next candidate.

Pseudo-code:

function solve(nums):
    if nums is empty: return 0
    max_coins = 0
    for i from 0 to length(nums) - 1:
        current_gain = nums[i-1] * nums[i] * nums[i+1]
        remaining = nums with index i removed
        max_coins = max(max_coins, current_gain + solve(remaining))
    return max_coins

Complexity Analysis: The time complexity is O(N!). For N = 300 (the problem constraint), this is computationally impossible. The factorial growth arises because at the first step we have N choices, then N-1, and so on. This approach will immediately result in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: DP - Interval DP

We will use a 2D array dp[i][j] to store the maximum coins collectible from the open interval (i, j) (balloons strictly between index i and index j).

1. Data Preparation: Create a new array A that includes the original nums but padded with 1 at the beginning and 1 at the end. This simplifies boundary handling. The new size is n + 2.
2. DP State Definition: dp[i][j] represents the max coins obtained by bursting all balloons between index i and j (exclusive of i and j).
3. Initialization: dp[i][j] = 0 for all i, j. This is implicitly true for ranges where j == i + 1 (no balloons between them).
4. Iteration (Interval DP):
   • Iterate through the length of the range from 1 to n.
   • Iterate through the left boundary from 0 to n - length + 1.
   • Calculate right = left + length + 1.
   • Iterate through all possible positions k between left and right.
5. Transition: For each k (the last balloon to burst in the interval), the total value is: dp[left][k] + dp[k][right] + (A[left] * A[k] * A[right]) We maximize dp[left][right] over all valid k.
6. Result: The answer is stored in dp[0][n + 1].

Execution Flow

1. Setup:

   • Input: [3, 1, 5, 8]
   • Augmented Array A: [1, 3, 1, 5, 8, 1] (Indices 0 to 5).
   • Initialize n x n DP table with zeros.

2. Window Size 1 (Ranges of 1 balloon):

   • Range (0, 2): Balloon at index 1 (Value 3). Last burst cost: 1*3*1. dp[0][2] = 3.
   • Range (1, 3): Balloon at index 2 (Value 1). Last burst cost: 3*1*5. dp[1][3] = 15.
   • Range (2, 4): Balloon at index 3 (Value 5). Last burst cost: 1*5*8. dp[2][4] = 40.
   • Range (3, 5): Balloon at index 4 (Value 8). Last burst cost: 5*8*1. dp[3][5] = 40.

3. Window Size 2 (Ranges of 2 balloons):

   • Range (0, 3): Balloons at indices 1, 2.
     • k=1 (3 is last): dp[0][1] + dp[1][3] + 1*3*5 = 0 + 15 + 15 = 30.
     • k=2 (1 is last): dp[0][2] + dp[2][3] + 1*1*5 = 3 + 0 + 5 = 8.
     • Max is 30. dp[0][3] = 30.
   • ... (Repeat for other windows of size 2, 3, and 4).

4. Final Calculation:

   • The loop continues until window size == n.
   • We compute dp[0][5], considering all k from 1 to 4.
   • This accumulates the optimal substructures to find the global maximum.

Proof of Correctness

The correctness relies on the Principle of Optimality. For the global range (0, n+1) to be optimal, the sub-ranges generated by splitting at the last balloon k must also be optimal.

Since we iterate through every possible k for every possible range length (increasing from 1 to n), we exhaustively check the "last burst" candidate for every sub-segment. By the time we compute a larger range, the values for all smaller contained ranges (left, k) and (k, right) are guaranteed to be computed and optimal. Therefore, dp[left][right] correctly stores the maximum possible value for that interval.

Pattern Reuse Notes

The Interval DP pattern used here is highly transferable.

• LeetCode 546: Remove Boxes: Similar to Burst Balloons, but the state requires an extra dimension to track contiguous boxes of the same color.
• Matrix Chain Multiplication: The canonical textbook example of Interval DP. We decide the last place to multiply two matrices to minimize operations.
• LeetCode 375: Guess Number Higher or Lower II: We minimize the worst-case cost by choosing a pivot (guess) and solving for the left and right intervals.

Reference Implementation

C++ Solution for LeetCode 312

1#include <vector>
2#include <algorithm>
3#include <iostream>
4
5using namespace std;
6
7class Solution {
8public:
9    int maxCoins(vector<int>& nums) {
10        int n = nums.size();
11        // Create a new array with padding 1s at both ends
12        vector<int> A(n + 2);
13        A[0] = 1;
14        A[n + 1] = 1;
15        for(int i = 0; i < n; i++) {
16            A[i + 1] = nums[i];
17        }
18
19        // dp[i][j] stores the max coins for the range (i, j) exclusive
20        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
21
22        // Iterate over the length of the range
23        for (int len = 1; len <= n; len++) {
24            // Iterate over the left boundary
25            for (int left = 0; left <= n - len + 1; left++) {
26                int right = left + len + 1;
27                
28                // Iterate over the pivot 'k' (the last balloon to burst)
29                for (int k = left + 1; k < right; k++) {
30                    int coins = dp[left][k] + dp[k][right] + A[left] * A[k] * A[right];
31                    dp[left][right] = max(dp[left][right], coins);
32                }
33            }
34        }
35
36        return dp[0][n + 1];
37    }
38};

Java Solution for LeetCode 312

1class Solution {
2    public int maxCoins(int[] nums) {
3        int n = nums.length;
4        // Create new array with padding
5        int[] A = new int[n + 2];
6        A[0] = 1;
7        A[n + 1] = 1;
8        for (int i = 0; i < n; i++) {
9            A[i + 1] = nums[i];
10        }
11
12        // dp[i][j] stores max coins for range (i, j) exclusive
13        int[][] dp = new int[n + 2][n + 2];
14
15        // Iterate over the length of the range
16        for (int len = 1; len <= n; len++) {
17            // Iterate over the left boundary
18            // We need to ensure right boundary doesn't exceed n + 1
19            for (int left = 0; left <= n - len; left++) {
20                int right = left + len + 1;
21                
22                // Iterate through all possible last balloons 'k'
23                for (int k = left + 1; k < right; k++) {
24                    int currentCoins = dp[left][k] + dp[k][right] 
25                                     + A[left] * A[k] * A[right];
26                    dp[left][right] = Math.max(dp[left][right], currentCoins);
27                }
28            }
29        }
30
31        return dp[0][n + 1];
32    }
33}

Python Solution for LeetCode 312

1class Solution:
2    def maxCoins(self, nums: List[int]) -> int:
3        n = len(nums)
4        # Pad the array with 1s
5        A = [1] + nums + [1]
6        
7        # dp[i][j] stores max coins for range (i, j) exclusive
8        # Size is (n+2) x (n+2)
9        dp = [[0] * (n + 2) for _ in range(n + 2)]
10        
11        # Iterate over the length of the range
12        for length in range(1, n + 1):
13            # Iterate over the left boundary
14            for left in range(n - length + 2):
15                right = left + length + 1
16                
17                # Iterate through all possible last balloons 'k'
18                # k must be between left and right
19                for k in range(left + 1, right):
20                    coins = dp[left][k] + dp[k][right] + A[left] * A[k] * A[right]
21                    dp[left][right] = max(dp[left][right], coins)
22                    
23        return dp[0][n + 1]