AlgoMaster Logo

Burst Balloons

hardFrequency9 min readUpdated June 23, 2026

Understanding the Problem

We have a row of balloons, each with a value. When we burst a balloon, we earn coins equal to the product of that balloon's value with its two neighbors. After bursting, the neighbors of the burst balloon become adjacent to each other. We need to find the order of bursting that maximizes total coins.

What makes this problem hard is that bursting a balloon changes the neighborhood of every remaining balloon. If you burst balloon i, balloons i-1 and i+1 become adjacent, so the coins from bursting balloon i+1 later depend on whether balloon i is already gone. Every burst changes the value of the bursts that follow.

Key Constraints:

  • 1 <= n <= 300 → Anything exponential is ruled out. An O(n^3) interval DP runs in roughly 27 million basic operations and fits within limits.
  • 0 <= nums[i] <= 100 → Values are non-negative. A single burst earns at most 100 100 100 = 1,000,000 coins, so 300 bursts total at most 3 * 10^8, which fits in a 32-bit integer.

Approach 1: Brute Force (Try All Permutations)

Intuition

Try every possible order of bursting. There are n balloons, so there are n! possible orderings. For each ordering, simulate the bursts, total the coins, and keep the maximum.

The simulation works recursively. Pick a balloon to burst, compute the coins using its current neighbors, remove it from the list, and recurse on the remaining balloons. Try every balloon as the first burst, then every remaining balloon as the second, and so on.

Algorithm

  1. For each remaining balloon in the current list, burst it.
  2. Compute the coins earned: left neighbor's value balloon's value right neighbor's value (using 1 for out-of-bounds).
  3. Remove the balloon from the list and recurse on the shorter list.
  4. Track the maximum coins across all recursive branches.
  5. Restore the balloon and try the next candidate.

Example Walkthrough

Input: nums = [3, 1, 5, 8]

One of the 4! = 24 orderings the recursion explores: burst the balloons in value order 1, 5, 3, 8.

  • Burst 1: neighbors are 3 and 5, coins = 315 = 15, remaining = [3, 5, 8]
  • Burst 5: neighbors are 3 and 8, coins = 358 = 120, remaining = [3, 8]
  • Burst 3: neighbors are the implicit boundary 1 and 8, coins = 138 = 24, remaining = [8]
  • Burst 8: both neighbors are implicit boundaries, coins = 181 = 8, remaining = []

This ordering totals 15 + 120 + 24 + 8 = 167. No other ordering beats it, so after exploring all 24 the recursion returns 167.

Code

The deeper problem is that no useful state survives between branches. After a few bursts the remaining balloons form an arbitrary subsequence of the original array, so even memoizing on the remaining set leaves up to 2^n distinct states. An efficient solution needs subproblems described by contiguous ranges, because there are only O(n^2) of those. The next approach finds such a decomposition.

Approach 2: Bottom-Up Interval DP

Intuition

To avoid special-casing the edges of the array, pad it with 1s on both ends: vals = [1, nums[0], nums[1], ..., nums[n-1], 1]. The padded boundaries are never burst; they only supply neighbor values.

Now fix a range with boundaries left and right and, instead of choosing which balloon inside it to burst first, choose which balloon k is burst last. At the moment k is burst, every other balloon in the range is already gone, so its neighbors are the boundaries themselves. That final burst earns vals[left] * vals[k] * vals[right], regardless of the order in which the interior was removed.

Choosing the last burst splits the range into two smaller ranges, (left, k) and (k, right), both of which must be emptied before k goes. Each has known boundaries that survive until it is empty (left and k on one side, k and right on the other), so each is the same problem on a smaller range.

Define dp[left][right] as the maximum coins obtainable by bursting all balloons strictly between indices left and right (exclusive). The answer is dp[0][m-1], where m = n + 2 is the padded length.

Algorithm

  1. Create a padded array: vals = [1] + nums + [1]. Let m = len(vals).
  2. Create a 2D DP table of size m x m, initialized to 0. Intervals with no balloon strictly inside keep the value 0.
  3. Iterate over interval lengths from 3 to m. The recurrence only reads dp[left][k] and dp[k][right], which span strictly shorter intervals, so processing lengths in increasing order guarantees both are final before they are read.
  4. For each interval (left, right) of the current length, try every balloon k between left+1 and right-1 as the last burst.
  5. For each k: dp[left][right] = max(dp[left][right], dp[left][k] + vals[left] * vals[k] * vals[right] + dp[k][right]).
  6. Return dp[0][m-1].

Example Walkthrough

Input: nums = [3, 1, 5, 8], padded to vals = [1, 3, 1, 5, 8, 1]. The animation below fills the DP table as interval lengths grow from 3 to 6.

vals (padded)
1Padded array: vals = [1, 3, 1, 5, 8, 1]. Boundaries (idx 0, 5) are never burst.
0
1
boundary
1
3
2
1
3
5
4
8
5
1
boundary
dp
1Initialize 6x6 DP table. Goal: dp[0][5].
0
1
2
3
4
5
0
0
0
0
0
0
goal
0
1
0
0
0
0
0
0
2
0
0
0
0
0
0
3
0
0
0
0
0
0
4
0
0
0
0
0
0
5
0
0
0
0
0
0
1/7

The table reaches dp[0][5] = 167. The winning splits also recover the optimal order: dp[0][5] chose k=4, so balloon 8 is burst last overall; dp[0][4] chose k=1, so balloon 3 goes last within that range; and dp[1][4] chose k=3, so balloon 5 goes after balloon 1. Unwinding gives the order 1, 5, 3, 8, the same ordering traced in Approach 1.

Code

The same recurrence can also be written top-down. The next approach memoizes the recursion directly, which removes the need to work out the table fill order.

Approach 3: Top-Down Memoization

Intuition

The recurrence is identical to Approach 2: solve(left, right) returns the maximum coins from bursting all balloons strictly between left and right, trying each k as the last burst and taking the maximum. The difference is mechanical. Instead of filling the table by increasing interval length, the function recurses into its two subintervals when it first needs them and caches each result. No fill order has to be chosen, and each of the O(n^2) intervals is still solved once.

Algorithm

  1. Pad the array with 1s: vals = [1] + nums + [1]. Let m = len(vals).
  2. Create a memoization table initialized to -1.
  3. Define solve(left, right): if right - left < 2, return 0. Otherwise, try each k from left+1 to right-1, compute solve(left, k) + vals[left]*vals[k]*vals[right] + solve(k, right), and return the max.
  4. Return solve(0, m-1).

Example Walkthrough

Input: nums = [3, 1, 5, 8], padded to vals = [1, 3, 1, 5, 8, 1]. The top-level call is solve(0, 5), which tries k = 1, 2, 3, 4.

The recursion is depth-first, so the first branch descends to the smallest intervals before anything is cached:

  • k=1: coins = 1\3\1 = 3. solve(0, 1) returns 0 (no balloons strictly inside). solve(1, 5) recurses and bottoms out at the one-balloon intervals, memoizing them as it returns: solve(3, 5) = 5\8\1 = 40, solve(2, 4) = 1\5\8 = 40, solve(1, 3) = 3\1\5 = 15. Combining them: solve(2, 5) = max(5+40, 40+8) = 48 (k=4), solve(1, 4) = max(24+40, 15+120) = 135 (k=3), and solve(1, 5) = max(0+3+48, 15+15+40, 135+24+0) = 159 (k=4). Candidate for k=1: 0 + 3 + 159 = 162.
  • k=2: coins = 1\1\1 = 1. solve(0, 2) = 1\3\1 = 3 (computed fresh), solve(2, 5) = 48 (memo hit). Candidate: 3 + 1 + 48 = 52.
  • k=3: coins = 1\5\1 = 5. solve(0, 3) = max(0+15+15, 3+5+0) = 30, reusing the cached solve(1, 3) = 15. solve(3, 5) = 40 (memo hit). Candidate: 30 + 5 + 40 = 75.
  • k=4: coins = 1\8\1 = 8. solve(0, 4) = max(0+24+135, 3+8+40, 30+40+0) = 159, reusing the cached solve(1, 4) = 135. solve(4, 5) = 0. Candidate: 159 + 8 + 0 = 167.

solve(0, 5) returns max(162, 52, 75, 167) = 167. The memo table ends up holding the same values as the bottom-up DP table, filled in depth-first order instead of by length.

Code