4.24.10 — Burst Balloons

LeetCode 312 · Hard

The problem

Balloons hold numbers. Bursting balloon i earns nums[left] × nums[i] × nums[right], where left and right are its current neighbours — the ones still unburst. Balloons outside the array count as 1. Maximise the total.

nums = [3,1,5,8]   →  167
    burst 1:  3×1×5  = 15    →  [3,5,8]
    burst 5:  3×5×8  = 120   →  [3,8]
    burst 3:  1×3×8  = 24    →  [8]
    burst 8:  1×8×1  = 8     →  []
    total 167

Up to 300 balloons.

Why the obvious approach fails

The natural state is "the best score for this set of remaining balloons", which is 2^n states — far too many.

The natural recursion is "which balloon do I burst first?" — and it does not work either, and understanding why is the whole problem.

When you burst a balloon first, the array splits into a left part and a right part — but they are not independent. After bursting the middle balloon, the balloons on either side become neighbours of each other, so what happens on the left changes the score on the right. The subproblems overlap in a way that cannot be separated, which means no clean recurrence.

The reversal that makes it work

Ask which balloon is burst LAST in a range, not first.

If balloon i is the last one to burst in the open range (left, right), then at that moment everything strictly between left and right is already gone, so i's neighbours are exactly left and right. Its score is a known number:

nums[left] \times nums[i] \times nums[right]

And now the two sides are independent. Everything in (left, i) was burst before i, with i still present as a wall, so that side never sees anything beyond i. Same on the right.

dp[left][right] = \max_{left < i < right}\Big( nums[left] \cdot nums[i] \cdot nums[right] + dp[left][i] + dp[i][right] \Big)

Choosing the last event instead of the first is what makes the subproblems separable. That reversal is the transferable idea, and it appears in several hard interval DPs.

Two setup details

Pad the array with 1s at both ends. The problem says out-of-range balloons count as 1, so [1] + nums + [1] removes every boundary check from the recurrence.

dp[left][right] uses an open interval — it covers the balloons strictly between left and right, and both endpoints stay unburst. Getting this convention wrong is where the off-by-one errors live, so state it before writing code.

The fill order, which is the real difficulty

dp[left][right] reads dp[left][i] and dp[i][right], both shorter ranges. So you must fill by increasing range length, not by row or column.

for length in range(2, n):          # gap between left and right
    for left in range(n - length):
        right = left + length

This is the standard interval DP loop shape, and it is worth recognising on sight: outer loop over length, inner loop over start position, end derived.

The solution

Python

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):                 # open-interval width
            for left in range(n - length):
                right = left + length

                for i in range(left + 1, right):   # i is burst LAST
                    dp[left][right] = max(
                        dp[left][right],
                        balloons[left] * balloons[i] * balloons[right]
                        + dp[left][i] + dp[i][right]
                    )

        return dp[0][n - 1]

TypeScript

function maxCoins(nums: number[]): number {
  const balloons = [1, ...nums, 1];
  const n = balloons.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));

  for (let length = 2; length < n; length++) {
    for (let left = 0; left + length < n; left++) {
      const right = left + length;

      for (let i = left + 1; i < right; i++) {
        dp[left][right] = Math.max(
          dp[left][right],
          balloons[left] * balloons[i] * balloons[right] + dp[left][i] + dp[i][right]
        );
      }
    }
  }

  return dp[0][n - 1];
}

length starts at 2, because an open interval needs at least one balloon strictly inside it.

dp[left][i] and dp[i][right] are both shorter than dp[left][right], so the length-ordered loop guarantees they are filled.

The answer is dp[0][n-1] — the whole padded array, with the two sentinel 1s as the outer walls.

Trace on [3,1,5,8]

Padded: [1,3,1,5,8,1].

The optimal order bursts 1, then 5, then 3, then 8 — meaning 8 is burst last overall. So the top-level split takes i as the index of 8, scoring 1 × 8 × 1 = 8, plus dp for everything to its left. That left range then chooses 3 as its last balloon, and so on.

Reading the answer as a nesting of "who went last" is what makes the recurrence believable.

The top-down version

from functools import lru_cache

def maxCoins(self, nums):
    balloons = [1] + nums + [1]

    @lru_cache(None)
    def best(left: int, right: int) -> int:
        if left + 1 == right:
            return 0
        return max(balloons[left] * balloons[i] * balloons[right]
                   + best(left, i) + best(i, right)
                   for i in range(left + 1, right))

    return best(0, len(balloons) - 1)

Easier to write and easier to trust, because you never work out the fill order — the recursion finds it. This is the case 4.22 makes for deriving top-down.

Complexity

O(n^3) time, and you can read that straight off the structure: O(n^2) states — one per (left, right) pair — times O(n) transitions, one per choice of the last balloon. That is the states × transitions formula.

O(n^2) space.

Where this goes next

Interval DP is a small family with a shared loop shape and a shared question — what is the last, or the outermost, thing to happen in this range?

• Matrix Chain Multiplication — the classic. Which multiplication happens last?
• Minimum Cost to Cut a Stick — which cut is made last?
• Strange Printer, Remove Boxes — same family, harder states.
• Longest Palindromic Subsequence — an interval DP where the question is about the two ends rather than a split point.

The recognition cue: a range, a choice of split point inside it, and O(n^3) allowed by the constraints. n ≤ 300 gives 2.7 \times 10^7, which is precisely an O(n^3) budget — the constraint is telling you the answer.

What the interviewer will push on

"Why does thinking about the first balloon fail?" The two sides become neighbours after the burst, so the subproblems are not independent. This is the question the problem exists to ask.

"Why does the last balloon work?" At the moment it bursts, everything inside is gone, so its neighbours are exactly the range's endpoints — and each side is then a self-contained subproblem.

"Why pad with 1s?" Out-of-range balloons count as 1, and padding removes every boundary check.

"What is the fill order and why?" By increasing range length, because each state reads shorter ranges.

"What is the complexity, and how do you know?" O(n^2) states times O(n) transitions.

One thing to volunteer: say the reversal out loud before anything else. "I will pick which balloon bursts last, not first, because that is what makes the two sides independent." Everything else on this page follows from that sentence, and an interviewer who hears it knows you have understood the problem rather than remembered it.

Next: 4.24.11 Regular Expression Matching — the last problem in the chapter, and the one with the most cases to get right.