AlgoMaster Logo

Burst Balloons

Last Updated: March 28, 2026

hard
5 min read

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 tricky is that bursting a balloon changes the neighborhood of every remaining balloon. If you burst balloon i, suddenly balloons i-1 and i+1 become neighbors. So the coins you earn from bursting balloon i+1 later depend on whether you already burst balloon i. The order of operations matters enormously, and every decision ripples forward.

The key observation: instead of thinking about which balloon to burst first, think about which balloon to burst last in a given range. If balloon k is the last one burst in the range (left, right), then when we burst it, its neighbors are exactly left and right (the boundaries). Everything else in that range is already gone. This "last burst" perspective eliminates the dependency problem and gives us clean subproblems.

Key Constraints:

  • 1 <= n <= 300 → With up to 300 balloons, we need O(n^3) or better. An O(n^3) interval DP fits perfectly within limits.
  • 0 <= nums[i] <= 100 → Values are non-negative. The maximum product for any single burst is 100 100 100 = 1,000,000. With 300 balloons, total coins fit comfortably in a 32-bit integer.

Approach 1: Brute Force (Try All Permutations)

Intuition

The most direct approach is to try every possible order of bursting. There are n balloons, so there are n! possible orderings. For each ordering, simulate the bursting process, calculate the total coins, and keep track of the maximum.

This is what you would naturally think of first. 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 to 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. Backtrack by reinserting the balloon and trying the next one.

Example Walkthrough

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

One possible bursting order: burst index 1 (value 1), then index 0 (value 3), then index 1 (value 5, now adjacent to boundary 1 and 8), then index 0 (value 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 1 and 8, coins = 138 = 24, remaining = [8]
  • Burst 8: neighbors are 1 and 1, coins = 181 = 8, remaining = []

Total = 15 + 120 + 24 + 8 = 167. The brute force tries all n! orderings and returns the max.

Code

We are trying every permutation, which is astronomically slow. Many different orderings lead to the same remaining set of balloons, but we recompute from scratch each time. Can we define subproblems over contiguous ranges instead?

Approach 2: Bottom-Up Interval DP

Intuition

The brute force stumbles because bursting a balloon changes the neighbors of every remaining balloon. Here is the mental shift that unlocks this problem: instead of asking "which balloon should I burst first?", ask "which balloon should I burst last in this range?"

If balloon k is the last balloon burst in the range between boundaries left and right, then at the moment we burst k, every other balloon in that range is already gone. The only balloons still standing near k are left and right themselves (the boundaries). So the coins from bursting k are exactly nums[left] * nums[k] * nums[right].

Everything to the left of k (between left and k) forms its own independent subproblem, and everything to the right of k (between k and right) forms another. These two subproblems do not interact because k is still standing while they are being resolved.

To make the boundary logic clean, pad the original array with 1s on both ends: [1, nums[0], nums[1], ..., nums[n-1], 1]. 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][n+1].

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.
  3. Iterate over interval lengths from 3 to m (we need at least one balloon between the boundaries).
  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

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
1/7
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

Code

This bottom-up approach fills every interval systematically. Can we express the same recurrence top-down, which is often easier to code correctly in an interview?

Approach 3: Top-Down Memoization

Intuition

The idea is identical to Approach 2: solve(left, right) returns the maximum coins from bursting all balloons strictly between left and right. We try each k as the last burst and take the maximum. The only difference is we recurse instead of looping over interval lengths, and memoize results.

Many people find this version easier to write under interview pressure because you do not need to think about the order of filling the table. Just write the recurrence naturally and let the recursion handle dependencies.

Algorithm

  1. Pad the array with 1s: vals = [1] + nums + [1].
  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

The recursive calls mirror the bottom-up table exactly. For nums = [3, 1, 5, 8], solve(0, 5) tries k=1,2,3,4. For k=4, it calls solve(0, 4) and solve(4, 5). The recursion bottoms out at intervals with no balloons between boundaries. The memoization ensures each subproblem is solved once, yielding the same answer: 167.

Code