LeetCode 312: Burst Balloons

Problem Restatement

We are given an integer array nums.

Each value represents a balloon.

When we burst balloon i, we gain coins equal to:

nums[i - 1] * nums[i] * nums[i + 1]

If the left or right neighbor is outside the array, treat that missing neighbor as 1.

After a balloon is burst, it disappears, so its left and right neighbors change.

Return the maximum coins we can collect by choosing the best bursting order.

The official constraints are 1 <= nums.length <= 300 and 0 <= nums[i] <= 100. The examples include nums = [3,1,5,8], whose answer is 167.

Input and Output

Function shape:

def maxCoins(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [3, 1, 5, 8]

One optimal order is:

[3,1,5,8] -> [3,5,8] -> [3,8] -> [8] -> []

Coins:

3*1*5 + 3*5*8 + 1*3*8 + 1*8*1
= 15 + 120 + 24 + 8
= 167

Output:

167

Example 2:

nums = [1, 5]

Burst 1 first:

1*1*5 = 5

Then burst 5:

1*5*1 = 5

Total:

10

Output:

10

First Thought: Try Every Burst Order

A direct solution tries every possible order.

For n balloons, there are many orders.

At the first step we can choose any of n balloons.

At the next step, any of n - 1 remaining balloons.

So this becomes roughly:

n!

This is far too large for n <= 300.

We need dynamic programming.

Why This Problem Feels Hard

If we think about the first balloon to burst, the subproblems are messy.

Suppose we burst one balloon first. Its two neighbors become adjacent. That changes future coin values.

So choosing the first burst does not cleanly split the array.

The trick is to think in reverse:

Choose the last balloon to burst inside an interval.

When a balloon is the last one left inside an interval, its two outside neighbors are fixed.

That makes the coin calculation stable.

Add Virtual Boundary Balloons

Add 1 to both ends:

arr = [1] + nums + [1]

For example:

nums = [3, 1, 5, 8]
arr = [1, 3, 1, 5, 8, 1]

These boundary balloons are never burst.

They only help compute coins at the edges.

DP Definition

Let:

dp[left][right]

mean:

Maximum coins we can get by bursting all balloons strictly between left and right.

So left and right are boundary balloons for the current interval.

They are not burst in this subproblem.

For example:

dp[0][5]

means:

Maximum coins from bursting all original balloons between the two virtual boundaries.

That is the final answer.

Last Balloon Choice

For interval (left, right), choose some balloon mid as the last balloon to burst inside this interval.

Before bursting mid, all balloons between left and mid are gone, and all balloons between mid and right are gone.

So at that moment, the neighbors of mid are exactly:

arr[left]

and:

arr[right]

Coins from bursting mid last:

arr[left] * arr[mid] * arr[right]

The left side contributes:

dp[left][mid]

The right side contributes:

dp[mid][right]

So the transition is:

dp[left][right] = max(
    dp[left][mid] + arr[left] * arr[mid] * arr[right] + dp[mid][right]
)

for every mid between left and right.

Algorithm

1. Build arr = [1] + nums + [1].
2. Create a 2D DP table filled with zeroes.
3. Process intervals by increasing length.
4. For each interval (left, right):
   • Try every mid between them.
   • Treat mid as the last balloon burst in this interval.
   • Update dp[left][right].
5. Return dp[0][n + 1].

Intervals with no balloon inside have value 0.

That means when:

right == left + 1

there is nothing to burst.

Correctness

For any interval (left, right), consider an optimal way to burst all balloons inside it.

Among those balloons, one balloon must be burst last. Call it mid.

When mid is burst last, every other balloon inside (left, right) has already disappeared. Therefore, its current neighbors are exactly left and right.

So the coins from the final burst are:

arr[left] * arr[mid] * arr[right]

All balloons between left and mid must have been burst before that final step. The best possible coins from them are dp[left][mid].

All balloons between mid and right must also have been burst before that final step. The best possible coins from them are dp[mid][right].

Thus every optimal solution for (left, right) has value:

dp[left][mid] + arr[left] * arr[mid] * arr[right] + dp[mid][right]

for some valid mid.

The algorithm tries every possible mid, so it considers the last balloon used by the optimal solution.

Since smaller intervals are computed before larger intervals, both subproblem values are already correct when needed.

Therefore, dp[left][right] is correct for every interval, and dp[0][n + 1] is the maximum coins for the whole array.

Complexity

This fits n <= 300.

Implementation

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        arr = [1] + nums + [1]
        n = len(arr)

        dp = [[0] * n for _ in range(n)]

        for length in range(2, n):
            for left in range(0, n - length):
                right = left + length

                best = 0

                for mid in range(left + 1, right):
                    coins = (
                        dp[left][mid]
                        + arr[left] * arr[mid] * arr[right]
                        + dp[mid][right]
                    )

                    best = max(best, coins)

                dp[left][right] = best

        return dp[0][n - 1]

Code Explanation

We add virtual boundary balloons:

arr = [1] + nums + [1]

They make every burst have a left and right neighbor.

Create the DP table:

dp = [[0] * n for _ in range(n)]

dp[left][right] stores the best result for the open interval (left, right).

We process by interval length:

for length in range(2, n):

Length 2 means there is exactly one balloon between left and right.

Choose the interval:

for left in range(0, n - length):
    right = left + length

Try each possible last balloon:

for mid in range(left + 1, right):

Compute the total if mid is burst last:

coins = (
    dp[left][mid]
    + arr[left] * arr[mid] * arr[right]
    + dp[mid][right]
)

Keep the best value:

best = max(best, coins)

Store it:

dp[left][right] = best

The final interval is between the two virtual boundaries:

return dp[0][n - 1]

Testing

def run_tests():
    s = Solution()

    assert s.maxCoins([3, 1, 5, 8]) == 167
    assert s.maxCoins([1, 5]) == 10
    assert s.maxCoins([1]) == 1
    assert s.maxCoins([0]) == 0
    assert s.maxCoins([0, 1, 0]) == 1
    assert s.maxCoins([9, 76, 64, 21]) == 116718

    print("all tests passed")

run_tests()

Test meaning: