312. Burst Balloons

Problem¶

Given balloon values nums, burst every balloon. Bursting a balloon earns its current value times its current left and right neighbors, treating missing neighbors as 1. Return the maximum total coins.

nums = [3, 1, 5, 8]
burst order: 1 -> 5 -> 3 -> 8
coins: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
output: 167

Key trick¶

Choose the last balloon burst in each interval, not the first. Its neighbors are then fixed interval boundaries, producing independent left and right subproblems.

Trap¶

Greedy choices based on immediate coins or balloon values are not globally optimal.
After bursting a balloon, its neighbors change.
Dividing the array product by the current value fails when that value is zero.
Mutating nums may unexpectedly alter the caller's input.

Why is it interesting?¶

Reversing the decision from "which balloon is first?" to "which balloon is last?" turns a changing-neighbor problem into standard interval dynamic programming.

Python solution¶

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        # Add permanent boundary balloons.
        vals = [1] + nums + [1]
        n = len(vals)

        # dp[l][r] is the maximum coins from bursting balloons
        # strictly between boundary indices l and r.
        dp = [[0] * n for _ in range(n)]

        # Process shorter open intervals before longer ones.
        for gap in range(2, n):
            for l in range(n - gap):
                r = l + gap

                # Let k be the last balloon burst inside (l, r).
                for k in range(l + 1, r):
                    coins = (
                        dp[l][k]
                        + vals[l] * vals[k] * vals[r]
                        + dp[k][r]
                    )
                    dp[l][r] = max(dp[l][r], coins)

        return dp[0][n - 1]

Time complexity: \(O(n^3)\).

Space complexity: \(O(n^2)\).

Comment on my solution¶

Correctly identifies that the problem has a global dependency and is unsuitable for a simple greedy strategy.
The idea of reversing the problem is the crucial insight, but it should mean selecting the last balloon in an interval.
left * x * right + product_of_remaining_values does not represent the best future reward, because later rewards depend on dynamically changing neighbors.
The heuristic can therefore discard the globally optimal burst order.
Division by x raises ZeroDivisionError when a balloon contains zero.
Recomputing math.prod(nums) inside nested loops is expensive.
nums.pop(idx) mutates the input list and makes each removal \(O(n)\).

import math

# Wrong Answer: 12 / 73 testcases passed
# [9,76,64,21,97]
# Output: 610329
# Expected: 669494
class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        # [3,1,5,8]
        # nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
        # coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

        ans = 0

        for _ in range(len(nums)):
            best = 1
            idx = 0
            for i, x in enumerate(nums):
                left = nums[i - 1] if i > 0 else 1
                right = nums[i + 1] if i < len(nums) - 1 else 1
                total = left * x * right
                total += math.prod(nums) // x
                if total >= best:
                    best = total
                    idx = i
                    triplet = left * x * right
            ans += triplet
            nums.pop(idx)

        return ans