LeetCode Problem 312

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

LeetCode 312, Burst Balloons

Problem Understanding

The problem gives us an array nums, where each element represents a balloon containing a number. When we burst a balloon at index i, we gain coins equal to:

$\text{coins} = nums[i-1] \times nums[i] \times nums[i+1]$

The important detail is that the neighbors of a balloon change dynamically as balloons are removed. After a balloon is burst, it disappears, and the remaining balloons become adjacent.

If a balloon does not have a left or right neighbor because it is at the boundary, we treat the missing neighbor as having value 1.

The goal is to determine the maximum number of coins we can collect by choosing the best order to burst all balloons.

The input consists of:

• An integer array nums
• nums[i] is the value painted on balloon i
• n can be as large as 300

The output is a single integer representing the maximum achievable coins.

The constraints are the key indicator that brute force will not work:

• There can be up to 300 balloons
• Every permutation of bursting order is potentially different
• 300! possible orders is astronomically large

This immediately suggests that we need a dynamic programming solution.

Several edge cases are important:

• Arrays of length 1
• Arrays containing zeros
• Arrays where all numbers are the same
• Cases where bursting a small balloon early enables larger multiplications later
• Boundary balloons, because they use virtual neighbors of value 1

A naive greedy approach can easily fail because local choices affect future neighbor relationships.

Approaches

Brute Force Approach

The brute force solution tries every possible order of bursting balloons.

At each step, we choose one balloon to burst, compute the coins gained from its current neighbors, remove it, and recursively solve the smaller problem. Since each recursive level can choose among remaining balloons, the total number of possibilities grows factorially.

This approach is correct because it exhaustively explores all valid bursting sequences and returns the maximum total.

However, it is far too slow. With n = 300, factorial complexity is impossible to compute within any practical time limit.

Key Insight for the Optimal Solution

The major difficulty comes from the fact that bursting a balloon changes neighboring relationships.

Instead of thinking about which balloon to burst first, the critical insight is to think about which balloon is burst last inside a subarray.

Suppose we are solving a subproblem for balloons between indices left and right.

If balloon k is the last balloon burst in that interval:

• Every other balloon inside (left, right) has already been removed
• At that moment, balloon k is adjacent only to left and right
• Therefore, the coins gained are fixed and easy to compute

This transforms a difficult dynamic problem into an interval dynamic programming problem.

To simplify boundary handling, we add virtual balloons with value 1 at both ends.

If the transformed array is:

[1] + nums + [1]

then the recurrence becomes:

$dp[left][right] = \max_{left < k < right} \left(dp[left][k] + dp[k][right] + nums[left] \times nums[k] \times nums[right]\right)$

This works because:

• dp[left][k] represents bursting everything between left and k
• dp[k][right] represents bursting everything between k and right
• k is burst last in the interval

The problem becomes a classic interval DP.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Tries every possible bursting order recursively
Optimal Dynamic Programming	O(n³)	O(n²)	Uses interval DP and chooses the last balloon burst

Algorithm Walkthrough

1. Create a new array with virtual boundary balloons.

We prepend and append 1 to the original array:

balloons = [1] + nums + [1]

This removes special handling for edge balloons because every balloon now always has valid neighbors. 2. Create a 2D DP table.

Let:

dp[left][right]

represent the maximum coins obtainable by bursting all balloons strictly between left and right.

The interval is open, meaning left and right themselves are not burst in this subproblem. 3. Iterate over interval lengths.

We solve smaller intervals before larger intervals because larger intervals depend on smaller ones.

For each interval (left, right):

• Try every possible balloon k between them
• Assume k is the last balloon burst in that interval

4. Compute the coins gained if k is last.

Since all balloons inside the interval except k are already gone:

balloons[left] * balloons[k] * balloons[right]

are the coins earned from bursting k. 5. Add results from subproblems.

The total becomes:

dp[left][k] + dp[k][right] + current_coins

because the left and right intervals are independent once k is fixed as the final balloon. 6. Store the maximum result.

We take the best possible choice of k:

dp[left][right] = max(...)

7. Return the answer.

The final answer is:

dp[0][n - 1]

where n is the size of the padded array.

Why it works

The core invariant is that when we choose balloon k as the last balloon burst in interval (left, right), its neighbors are guaranteed to be exactly left and right. That makes the coin gain deterministic.

Because every valid bursting sequence has exactly one last balloon for every interval, the recurrence explores all possibilities without duplication. The DP table ensures each interval is solved once, giving both correctness and efficiency.

Python Solution

from typing import List

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

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

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

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

                    dp[left][right] = max(dp[left][right], coins)

        return dp[0][n - 1]

The implementation begins by adding virtual balloons with value 1 to both ends of the array. This simplifies boundary conditions because every balloon always has neighbors.

The dp table stores solutions for intervals. Initially, all values are 0 because empty intervals produce no coins.

The outer loop iterates through interval sizes from small to large. This ordering is essential because larger intervals depend on smaller subproblems already being solved.

For each interval (left, right), the algorithm tries every possible balloon k as the last balloon burst in that interval.

The recurrence combines:

• The optimal result from the left subinterval
• The optimal result from the right subinterval
• The coins gained from bursting k last

Finally, dp[0][n - 1] contains the best possible answer for the entire array.

Go Solution

func maxCoins(nums []int) int {
	balloons := make([]int, 0, len(nums)+2)
	balloons = append(balloons, 1)

	for _, num := range nums {
		balloons = append(balloons, num)
	}

	balloons = append(balloons, 1)

	n := len(balloons)

	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	for length := 2; length < n; length++ {
		for left := 0; left < n-length; left++ {
			right := left + length

			for k := left + 1; k < right; k++ {
				coins := dp[left][k] +
					dp[k][right] +
					balloons[left]*balloons[k]*balloons[right]

				if coins > dp[left][right] {
					dp[left][right] = coins
				}
			}
		}
	}

	return dp[0][n-1]
}

The Go implementation follows the same interval dynamic programming strategy as the Python solution.

Slices are used instead of Python lists, and the 2D DP table is initialized manually using nested make calls.

Go integers are sufficient for this problem because the maximum possible answer fits within standard integer limits under the given constraints.

Worked Examples

Example 1

nums = [3,1,5,8]

After padding:

balloons = [1,3,1,5,8,1]

We build the DP table gradually.

Length = 2

Intervals with exactly one balloon inside.

Interval	Last Balloon	Coins	DP Value
(0,2)	1	1×3×1 = 3	3
(1,3)	2	3×1×5 = 15	15
(2,4)	3	1×5×8 = 40	40
(3,5)	4	5×8×1 = 40	40

Length = 3

Consider interval (1,4):

Possible last balloons:

k	Calculation	Total
2	dp[1][2] + dp[2][4] + 3×1×8	0 + 40 + 24 = 64
3	dp[1][3] + dp[3][4] + 3×5×8	15 + 0 + 120 = 135

Best value:

dp[1][4] = 135

Full Result

Eventually:

dp[0][5] = 167

Final answer:

167

Example 2

nums = [1,5]

After padding:

balloons = [1,1,5,1]

Possible orders:

Burst 1 first:

1×1×5 = 5
1×5×1 = 5
Total = 10

Burst 5 first:

1×5×1 = 5
1×1×1 = 1
Total = 6

Optimal answer:

10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n³)	Three nested loops: interval length, left boundary, and last balloon choice
Space	O(n²)	DP table stores results for all intervals

The DP table contains O(n²) states because every pair (left, right) defines an interval.

For each interval, we iterate through every possible last balloon k, adding another factor of O(n).

Therefore, the total time complexity becomes O(n³).

With n <= 300, this complexity is acceptable.

Test Cases

from typing import List

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

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

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

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

                    dp[left][right] = max(dp[left][right], coins)

        return dp[0][n - 1]

solution = Solution()

assert solution.maxCoins([3, 1, 5, 8]) == 167  # provided example
assert solution.maxCoins([1, 5]) == 10  # provided example
assert solution.maxCoins([1]) == 1  # single balloon
assert solution.maxCoins([0]) == 0  # single zero balloon
assert solution.maxCoins([0, 1, 5]) == 10  # zero inside array
assert solution.maxCoins([1, 1, 1, 1]) == 4  # all identical values
assert solution.maxCoins([9]) == 9  # single large value
assert solution.maxCoins([2, 3]) == 9  # small two-element case
assert solution.maxCoins([8, 2, 6, 8, 1]) == 560  # larger mixed case
assert solution.maxCoins([7, 9, 8, 0, 7, 1, 3, 5]) == 1358  # stress-style case

Test Summary

Test	Why
[3,1,5,8]	Validates standard example
[1,5]	Smallest non-trivial case
[1]	Single balloon handling
[0]	Zero-value balloon
[0,1,5]	Ensures zeros are handled correctly
[1,1,1,1]	Repeated identical values
[9]	Single large balloon
[2,3]	Small interval correctness
[8,2,6,8,1]	Complex mixed interactions
[7,9,8,0,7,1,3,5]	Larger stress scenario

Edge Cases

Single Balloon

When the input contains only one balloon, the algorithm must correctly treat its neighbors as virtual balloons with value 1.

For example:

nums = [5]

The result should be:

1 × 5 × 1 = 5

Without boundary padding, implementations often produce index errors or incorrect neighbor calculations. The padded array technique handles this naturally.

Balloons Containing Zero

Zero-valued balloons can dramatically change the optimal bursting order.

For example:

nums = [0, 1, 5]

Bursting the zero too late may eliminate opportunities for larger products. A greedy approach can easily fail here.

The interval DP solution explores every possible last balloon for every interval, guaranteeing that zero values are handled correctly.

Very Small Intervals

Intervals with only one balloon inside are the base building blocks of the DP table.

For interval (left, right) where:

right = left + 2

there is exactly one possible balloon to burst last.

Incorrect interval iteration order can leave required subproblems uncomputed. By processing intervals in increasing length order, the implementation guarantees all dependencies are already solved before they are needed.