Burst Balloons (LC 312)

Problem Statement

You are given n balloons, each with a number nums[i] painted on it. When you burst the i-th balloon, you gain nums[left] * nums[i] * nums[right] coins, where left and right are the adjacent unburst balloons. After bursting, left and right become adjacent. Out-of-range neighbors are treated as 1.

Return the maximum coins you can collect.

Example 1:

Input:  nums = [3, 1, 5, 8]
Output: 167
Explanation:
Burst 1 → 3*1*5 = 15,  nums = [3, 5, 8]
Burst 5 → 3*5*8 = 120, nums = [3, 8]
Burst 3 → 1*3*8 = 24,  nums = [8]
Burst 8 → 1*8*1 = 8
Total = 15 + 120 + 24 + 8 = 167.

Example 2:

Input:  nums = [1, 5]
Output: 10

Constraints:

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

Difficulty: Hard

---

Pattern Recognition

• Input structure: 1D array where elements mutate as you burst them.
• What are we optimizing? maximum coin total.
• Pattern: interval DP. The "burst last" perspective unlocks it.
• Why: Bursting first couples choices (which neighbors disappear affects future decisions). Bursting last decouples them: if you fix the balloon k you pop last in range (i, j), then the contribution nums[i] * nums[k] * nums[j] is final — everything else is two independent subproblems (i, k) and (k, j).

This "fix the last action" trick is a Google signature and appears in matrix-chain multiplication, optimal BST, and others.

---

Approach

Brute Force — All Permutations

Try every order of bursts. O(n!). Infeasible beyond tiny n.

Optimal — Interval DP on Last-to-Burst

Key Insight: Pad the array with sentinel 1s: balloons = [1] + nums + [1]. Define dp[i][j] = max coins from bursting all balloons strictly between i and j (exclusive of both). For each k in (i, j), consider k as the last burst — yielding balloons[i] * balloons[k] * balloons[j] + dp[i][k] + dp[k][j].

Recurrence:

dp[i][j] = max over k in (i+1 .. j-1) of:
           balloons[i] * balloons[k] * balloons[j] + dp[i][k] + dp[k][j]

Base case: dp[i][j] = 0 when j - i < 2 (no balloons between).

Fill order: by increasing interval length len = j - i from 2 up to n + 1.

Time: O(n^3) — two indices for the interval, one for k. Space: O(n^2).

Answer: dp[0][n + 1].

---

Walkthrough

nums = [3, 1, 5, 8], padded: [1, 3, 1, 5, 8, 1].

Length 2 intervals (no balloons between): dp[i][i+2] = 1 * nums[i+1] * 1? Not quite — dp[i][i+2] covers exactly one balloon between, index i+1.

i	j	k choices	compute
0	2	k=1	131 + 0 + 0 = 3
1	3	k=2	315 + 0 + 0 = 15
2	4	k=3	158 + 0 + 0 = 40
3	5	k=4	581 + 0 + 0 = 40

Length 3: two balloons between.

For (i, j) = (0, 3):

• k=1: 1*3*5 + dp[0][1] + dp[1][3] = 15 + 0 + 15 = 30.
• k=2: 1*1*5 + dp[0][2] + dp[2][3] = 5 + 3 + 0 = 8.
• Best: 30.

For (0, 4):

• k=1: 1*3*8 + dp[0][1] + dp[1][4].
• k=2: 1*1*8 + dp[0][2] + dp[2][4].
• k=3: 1*5*8 + dp[0][3] + dp[3][4].

... continue until length 5 (= n + 1), yielding dp[0][5] = 167.

Full hand trace is long but mechanical. The invariant: every cell only references shorter intervals, which are fully computed.

---

Implementation

TypeScript

function maxCoins(nums: number[]): number {
    const balloons = [1, ...nums, 1];
    const n = balloons.length;
    // dp[i][j] = max coins from bursting all balloons strictly between i and j
    const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));

    for (let len = 2; len < n; len++) {
        for (let i = 0; i + len < n; i++) {
            const j = i + len;
            let best = 0;
            for (let k = i + 1; k < j; k++) {
                const coins = balloons[i] * balloons[k] * balloons[j] + dp[i][k] + dp[k][j];
                if (coins > best) best = coins;
            }
            dp[i][j] = best;
        }
    }
    return dp[0][n - 1];
}

C++

int maxCoins(vector<int>& nums) {
    vector<int> balloons = {1};
    balloons.insert(balloons.end(), nums.begin(), nums.end());
    balloons.push_back(1);
    int n = balloons.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int len = 2; len < n; len++) {
        for (int i = 0; i + len < n; i++) {
            int j = i + len;
            int best = 0;
            for (int k = i + 1; k < j; k++) {
                int coins = balloons[i] * balloons[k] * balloons[j] + dp[i][k] + dp[k][j];
                if (coins > best) best = coins;
            }
            dp[i][j] = best;
        }
    }
    return dp[0][n - 1];
}

Watch out:

1. Trying to solve "which balloon to burst first" leads to coupling and wrong recurrence. Always think last burst.
2. Forgetting the sentinel 1s on both ends ignores the boundary-multiplier-1 rule.
3. Iteration order matters: you must fill shorter intervals before longer ones. Going by len is the safest order.

---

Complexity Analysis

	Time	Space
Brute (permutations)	O(n!)	O(n)
Interval DP	O(n^3)	O(n^2)

Bottleneck: three nested loops — i, j, k. At n = 300, n^3 = 2.7 * 10^7, very comfortable.

---

Edge Cases

1. n = 1 — pad to [1, x, 1]; answer 1 * x * 1 = x.
2. Array with zeros — zeros contribute 0 when popped; ensure multiplications still execute (they do).
3. All equal values — DP still works; no short-circuit needed.
4. Already sorted ascending / descending — no special case.
5. Max n = 300 — O(n^3) is safe; do not attempt memoized DFS in languages with slow recursion.
6. Values include zero right next to large values — the DP explores all orderings; no greedy shortcut beats it.

---

Related Problems

• LC 1039 — Minimum Score Triangulation of Polygon — Identical interval DP structure.
• LC 1000 — Minimum Cost to Merge Stones — Interval DP with an extra dimension for pile count.
• LC 87 — Scramble String — Different problem, same interval-partition mental model.
• LC 1547 — Minimum Cost to Cut a Stick — Direct analog: pad with sentinel endpoints, DP on intervals.

---

What Is Expected at Each Level

Junior: Typically stuck. Needs hints: "think about what balloon you burst last." With help, reaches the recurrence.

Mid-level: Derives the recurrence, implements the 3-loop DP, states O(n^3) correctly.

Senior (L4 target): Articulates the "fix the last action" trick cleanly, handles sentinels confidently, connects to LC 1547 and LC 1039 as same-shape problems. Discusses that memoized top-down is easier to write but iterative bottom-up is safer at n = 300 in Python-like languages due to recursion overhead.