150NeetCode 150

120.Burst Balloons

Hard2-D Dynamic Programming · 10/11
LeetCode #312Video

Problem

You have n balloons in a row, balloon i painted with the number nums[i]. When you burst balloon i you earn nums[left] * nums[i] * nums[right] coins, where left and right are the balloons currently adjacent to i (after earlier bursts). If a neighbour does not exist, treat it as a balloon with value 1.

Burst all the balloons and return the maximum coins you can collect.

Examples

Input:  nums = [3, 1, 5, 8]
Output: 167
Explanation: [3,1,5,8] → burst 1: 3*1*5 = 15
             [3,5,8]   → burst 5: 3*5*8 = 120
             [3,8]     → burst 3: 1*3*8 = 24
             [8]       → burst 8: 1*8*1 = 8
             total = 15 + 120 + 24 + 8 = 167
Input:  nums = [1, 5]
Output: 10
Explanation: burst 1 first (1*1*5 = 5), then 5 (1*5*1 = 5) = 10.

Constraints

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

💡 Key Insight

Choosing which balloon to burst first is hopeless — afterwards its two neighbours become adjacent and the subproblems are entangled. Instead choose which balloon k to burst last in an open interval (l, r): while every other balloon between l and r is being burst, k is still standing, so the left part (l, k) and right part (k, r) are completely independent. When k finally bursts, its neighbours are exactly the boundaries l and r. Pad the array with 1 on both ends and:

dp[l][r] = max over l < k < r of ( dp[l][k] + vals[l] * vals[k] * vals[r] + dp[k][r] )

Brute Force (Try Every Burst Order)

TimeO(n · n!)SpaceO(n)

Intuition

Simulate literally: pick any remaining balloon to burst next, collect its coins from its current neighbours, recurse on the remaining list, and undo. This explores all n! orders.

Algorithm

  1. best(list): if the list is empty return 0.
  2. For each index i in the list: coins = left * list[i] * right (using 1 beyond the ends); remove list[i], recurse, add it back; keep the max of coins + recursive result.
  3. Return best(nums as list).

Visualization

flowchart TD
    A["[1,5]"] -->|"burst 1: 1*1*5 = 5"| B["[5]"]
    A -->|"burst 5: 1*5*1 = 5"| C["[1]"]
    B -->|"burst 5: 1*5*1 = 5"| D["total 10"]
    C -->|"burst 1: 1*1*1 = 1"| E["total 6"]
    D --> F["max = 10"]
    E --> F

Code

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

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

    private int best(List<Integer> list) {
        if (list.isEmpty()) {
            return 0;
        }
        int result = 0;
        for (int i = 0; i < list.size(); i++) {
            int left = i > 0 ? list.get(i - 1) : 1;
            int right = i < list.size() - 1 ? list.get(i + 1) : 1;
            int coins = left * list.get(i) * right;
            int removed = list.remove(i);      // burst balloon i
            result = Math.max(result, coins + best(list));
            list.add(i, removed);              // undo
        }
        return result;
    }
}

Complexity

  • Time: O(n · n!) — every permutation of burst order, with O(n) list work per step.
  • Space: O(n) — recursion depth and the list.

Complexity Comparison

Approach Time Space
Brute Force (Try Every Burst Order) O(n · n!) O(n)
Top-Down Memoization (Interval DP) O(n³) O(n²)
Bottom-Up Interval DP O(n³) O(n²)

Common Pitfalls

  • Choosing the balloon burst first in an interval — its neighbours then depend on outside choices, so subproblems are not independent. Always choose the last one.
  • Using closed intervals without padding — the boundary multipliers vals[l] and vals[r] must be balloons that are still present (or the virtual 1s).
  • Iterating l from 0 upward with r growing in the outer loop incorrectly — fill by increasing length (or l descending, r ascending) so dependencies are ready.
  • Treating 0-valued balloons specially — they just contribute 0 coins; the DP handles them.
  • Forgetting that the answer is dp[0][n+1] on the padded array, not dp[0][n-1].