LeetCode #312 Hard

Burst Balloons

Choose a balloon-bursting order that maximizes the total coins collected.

arrayinterval-dpdynamic-programming

02

Intuition

Choosing the largest balloon first is unreliable because every burst changes its neighbors. It is difficult to describe the first burst of an interval, but easy to describe the last one: its two boundary balloons are then known and still present. Fixing the last balloon splits the remaining work into independent left and right intervals. Interval dynamic programming tests every possible last balloon and retains the best total.

How to spot this pattern

When removing an item changes who becomes adjacent, reverse the decision and ask which item is removed last. If that last choice separates an interval into independent sides, interval DP is the standard pattern.

03

Approach

1

Add permanent boundary balloons

Place value one before and after nums. These sentinels make every original balloon use the same formula, including balloons at the original ends.

2

Define an open interval subproblem

Let solve(left, right) be the maximum coins from bursting balloons strictly between boundary indices left and right. An empty interval returns zero.

3

Choose which balloon survives until last

For each middle inside the interval, combine the best left interval, the coins values[left] values[middle] values[right], and the best right interval. Memoize the maximum over all choices.

04

Solution

▶1class Solution:
▶2    def maxCoins(self, nums: List[int]) -> int:
▶3        values = [1] + nums + [1]
▶4 
▶5        @cache
▶6        def solve(left, right):
▶7            if left + 1 == right:
▶8                return 0
▶9            best = 0
▶10            for middle in range(left + 1, right):
▶11                coins = values[left] * values[middle] * values[right]
▶12                coins += solve(left, middle) + solve(middle, right)
▶13                best = max(best, coins)
▶14            return best
▶15 
▶16        return solve(0, len(values) - 1)

05

Common pitfalls

Modeling the first burst

✗ Wrong

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

✓ Right

coins = values[left] * values[middle] * values[right]

Original adjacent indices do not remain adjacent after earlier removals; boundaries are known only for the last burst.

Including boundaries in recursive work

✗ Wrong

solve(left, middle) + solve(middle, right) + solve(middle, middle)

✓ Right

solve(left, middle) + solve(middle, right)

The middle balloon is handled as the last burst and must not appear in either open subinterval.

Omitting sentinel balloons

✗ Wrong

values = nums

✓ Right

values = [1] + nums + [1]

Sentinels provide the required outside neighbor value for end balloons.

06

Edge cases

No balloons

The padded array has no interior index, so the open interval returns zero.

One balloon

It is last between the two sentinels and earns its own value.

Zero-valued balloons

They participate normally; alternative last choices can avoid relying on their zero product.

07

Complexity

Time

O(n^3)

Space

O(n^2)

There are O(n^2) intervals and each tests O(n) possible final balloons.