Burst Balloons

NeetCode: Burst Balloons · LeetCode: 312. Burst Balloons · Difficulty: Hard

You have n balloons with numbers nums[i] (an int[]; the method is int maxCoins(int[] nums)). Bursting balloon i earns nums[i-1] * nums[i] * nums[i+1] coins, where a neighbour outside the array counts as 1. After a burst, the neighbours become adjacent. Return the maximum coins from bursting all balloons.

Example

Text

Input:  nums = [3, 1, 5, 8]    Output: 167   (burst 1, 5, 3, 8: 15 + 120 + 24 + 8)
Input:  nums = [1, 5]          Output: 10

Brute force: try every bursting order

Try each balloon as the next one to burst, collect its coins from its current neighbours, remove it and recurse on what is left. The code keeps the balloons in an ArrayList<Integer>; remove(i) with an int argument removes by index, and add(i, v) puts the balloon back after the recursive call. Each remove and add shifts elements, which costs O(n) and is dominated by the O(n!) branching. That explores every ordering of the balloons.

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
    private int burst(List<Integer> nums) {
        if (nums.isEmpty()) {
            return 0;
        }
        int best = 0;
        for (int i = 0; i < nums.size(); i++) {
            int left = i > 0 ? nums.get(i - 1) : 1;
            int right = i + 1 < nums.size() ? nums.get(i + 1) : 1;
            int v = nums.remove(i); // remove(int index) returns the removed element
            int gain = left * v * right + burst(nums);
            nums.add(i, v);
            best = Math.max(best, gain);
        }
        return best;
    }

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

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxCoins(new int[] {3, 1, 5, 8}));
        System.out.println(sol.maxCoins(new int[] {1, 5}));
        System.out.println(sol.maxCoins(new int[] {7}));
        System.out.println(sol.maxCoins(new int[] {}));
    }
}

Output

Time: O(n!). Space: O(n).

Better: think about the last balloon (memoised)

Reverse the question. Bursting a balloon first changes its neighbours' neighbours, so the leftover problem cannot be split. Instead ask which balloon is burst last in an interval.

Pad the array with a 1 on each end (a new int[] of length n + 2). In the memoised version, -1 in the table means not computed, since a real result is never negative. Let solve(l, r) be the best coins from bursting everything strictly between l and r. If k is the last balloon burst in that gap, its neighbours at that moment are exactly l and r, and the balloons in (l, k) and (k, r) were burst earlier and independently:

solve(l, r) = max over k in (l, r) of solve(l, k) + solve(k, r) + v[l] * v[k] * v[r]

For [3, 1, 5, 8], padded to [1, 3, 1, 5, 8, 1], solve(0, 5) tries each k as the last balloon; k = 4 (the 8) gives solve(0, 4) + solve(4, 5) + 1 * 8 * 1.

Java

class Solution {
    private int solve(int[] v, int l, int r, int[][] memo) {
        if (r - l < 2) {
            return 0; // nothing strictly between l and r
        }
        if (memo[l][r] >= 0) {
            return memo[l][r]; // -1 means not computed
        }
        int best = 0;
        for (int k = l + 1; k < r; k++) {
            int coins = solve(v, l, k, memo) + solve(v, k, r, memo) + v[l] * v[k] * v[r];
            best = Math.max(best, coins);
        }
        memo[l][r] = best;
        return best;
    }

    public int maxCoins(int[] nums) {
        int m = nums.length + 2;
        int[] v = new int[m];
        v[0] = 1;
        v[m - 1] = 1;
        System.arraycopy(nums, 0, v, 1, nums.length);
        int[][] memo = new int[m][m];
        for (int[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        return solve(v, 0, m - 1, memo);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxCoins(new int[] {3, 1, 5, 8}));
        System.out.println(sol.maxCoins(new int[] {1, 5}));
        System.out.println(sol.maxCoins(new int[] {7}));
        System.out.println(sol.maxCoins(new int[] {}));
    }
}

Output

Time: O(n^3): O(n^2) intervals, up to n choices of k each. Space: O(n^2) table plus O(n) recursion depth.

Optimal: bottom-up interval DP

Fill dp[l][r] by increasing gap length r - l = 2, 3, .... Both dp[l][k] and dp[k][r] have a shorter gap than dp[l][r], so they are already computed. The recurrence is the same as above, without recursion.

Java

class Solution {
    public int maxCoins(int[] nums) {
        int m = nums.length + 2;
        int[] v = new int[m];
        v[0] = 1;
        v[m - 1] = 1;
        System.arraycopy(nums, 0, v, 1, nums.length);
        // dp[l][r]: best coins from bursting everything strictly between l and r
        int[][] dp = new int[m][m];
        for (int gap = 2; gap < m; gap++) {
            for (int l = 0; l + gap < m; l++) {
                int r = l + gap;
                int best = 0;
                for (int k = l + 1; k < r; k++) {
                    best = Math.max(best, dp[l][k] + dp[k][r] + v[l] * v[k] * v[r]);
                }
                dp[l][r] = best;
            }
        }
        return dp[0][m - 1];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxCoins(new int[] {3, 1, 5, 8}));
        System.out.println(sol.maxCoins(new int[] {1, 5}));
        System.out.println(sol.maxCoins(new int[] {7}));
        System.out.println(sol.maxCoins(new int[] {}));
    }
}

Output

Time: O(n^3). Space: O(n^2). The table cannot shrink to a single row because dp[l][r] reads entries from many different rows and columns.

Edge cases

Empty input returns 0; a single balloon returns its own value (both neighbours are the padding 1).
Balloons with value 0 are handled by the same recurrence.
Products of three values up to 100 are summed over up to 300 balloons: each burst is worth at most 100 * 100 * 100 = 10^6, The total is an int sum, which wraps silently on overflow, so much larger values or many more balloons would need long.

How to explain it in an interview

Start with the brute force: try every bursting order, O(n!). The neighbours change after each burst, which makes the problem hard to split.
Key insight: pick the last balloon burst in an interval. Its neighbours are then the interval ends, so the two sides are independent subproblems.
Steps: pad with 1 on both ends; loop k from l+1 to r-1; coins are dp[l][k] + dp[k][r] + v[l]*v[k]*v[r]; fill by increasing gap (or memoise on (l, r)).
Complexity: O(n^3) time, O(n^2) space.
Pitfall: choosing the first balloon fails because the halves are no longer independent. The bounds are exclusive: l and r are never burst inside solve(l, r).