Burst Balloons

Burst Balloons is a famous hard interview question. It traps almost everyone the first time. The natural instinct is to ask “which balloon should I burst first?” That instinct is exactly the wrong one. The secret is to flip the question and ask which balloon you burst last. Once you see that flip, a tangled problem turns into a clean table.

🎯 The Problem

You have a row of balloons, each with a number painted on it. You burst them one by one to earn coins. Your job is to burst all balloons in the best order to earn the most coins total.

• Bursting a balloon earns left * self * right coins.
• That is the balloon’s number times its left neighbor times its right neighbor.
• When a balloon bursts, its neighbors become next to each other. So the neighbors change as you go.
• If a neighbor is missing, because you burst it or it is off the edge, treat that side as a balloon with the number 1.

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

Explanation: a best order is
  burst 1 -> 3 * 1 * 5 = 15,   row becomes [3, 5, 8]
  burst 5 -> 3 * 5 * 8 = 120,  row becomes [3, 8]
  burst 3 -> 1 * 3 * 8 = 24,   row becomes [8]
  burst 8 -> 1 * 8 * 1 = 8,    row becomes []
  total = 15 + 120 + 24 + 8 = 167

We pad both ends with a 1. So the real working row is [1, 3, 1, 5, 8, 1]. The two extra 1s are the imaginary balloons off the edges. They make the coin math the same everywhere.

Here is the picture of the question. A row of balloons, each burst earning left times self times right.

🐢 Approach 1: Try Every Order (Brute Force)

The idea in one line: try every possible order of bursting and keep the best total.

The idea:

• Pick a balloon to burst first. Earn its coins.
• Solve the smaller row that is left. Try that for every first choice.

How it works:

• For each balloon, burst it first, then recurse on what remains.
• Keep the largest total over all first choices.

Why it is weak:

• For n balloons there are about n! orders, which is n factorial.
• That is n times n-1 times n-2 down to 1. Even ten balloons becomes millions of orders.
• The neighbors keep changing, so bursting a middle balloon shifts coins far away.
• The sub-problems overlap in a messy way, so you cannot reuse them.

Here is the try-every-burst-order code:

def max_coins(nums):
    def dfs(arr):
        if not arr:
            return 0
        best = 0
        for i in range(len(arr)):
            left = arr[i - 1] if i > 0 else 1
            right = arr[i + 1] if i + 1 < len(arr) else 1
            best = max(best, left * arr[i] * right + dfs(arr[:i] + arr[i + 1:]))
        return best

    return dfs(nums)

⚡ Approach 2: Last Balloon Insight Plus Memoization (Better)

The idea in one line: instead of which balloon to burst first, ask which to burst last in a range.

The idea:

• Look at balloons between two edges, left and right, not counting the edges.
• Say balloon k is the very last one burst in that range.

Why it works:

• By the time you burst k, every other balloon in the range is gone.
• So k’s neighbors are exactly left and right. They do not move.
• The coins for bursting k last are fixed at nums[left] * nums[k] * nums[right].
• Picking the last balloon freezes its neighbors and splits the range into two independent pieces.

How it works:

• Try every k as the last balloon and keep the best.
• The left piece and the right piece never touch, because k is the wall between them.
• Store each range’s answer in a table so you never redo it. That storing is memoization.

Here is the memoized interval code:

from functools import lru_cache


def max_coins(nums):
    nums = [1] + nums + [1]

    @lru_cache(None)
    def dfs(left, right):
        if left + 1 == right:
            return 0
        best = 0
        for last in range(left + 1, right):
            coins = nums[left] * nums[last] * nums[right]
            best = max(best, coins + dfs(left, last) + dfs(last, right))
        return best

    return dfs(0, len(nums) - 1)

🚀 Approach 3: Bottom-Up Interval DP (Best)

The idea in one line: build the same answer from the bottom up, filling a table of ranges.

The idea:

• Each cell stands for a range, also called an interval, of the row. This is interval DP.
• Pad the row with a 1 on each side.
• dp[left][right] holds the most coins from bursting every balloon strictly between left and right.
• The edges are not burst. They are only used as multipliers.

How it works:

• Fill the table by range length, from small ranges to big ones.
• For each range, try every balloon k strictly inside as the last one to burst.
• Value for that choice: dp[left][k] + nums[left] * nums[k] * nums[right] + dp[k][right].
• The first part is the best from the left sub-range. The middle is k burst last. The last is the right sub-range.
• Keep the largest value over all k.

Why it is best:

• Long ranges reuse the answers of their shorter sub-ranges.
• No recursion stack, just a clean table filled in order.
• Three nested loops give O(n³) time, far better than factorial.

Here is a dry run of the ranges we build, smallest first, growing up to the full row.

Steps to Solve

1. Make a new array that is nums with a 1 added at the front and a 1 added at the back.
2. Let N be the length of this padded array. Make a grid dp of size N by N, all zeros.
3. Loop over range length from 2 up, so the range has at least one balloon inside.
4. For each left, set right = left + length.
5. For each k strictly between left and right, compute dp[left][k] + nums[left]*nums[k]*nums[right] + dp[k][right].
6. Store the largest such value in dp[left][right].
7. The answer is dp[0][N-1], the full range from edge to edge.

#include <stdio.h>

int maxCoins(int *nums, int n) {
    int pad[64];
    pad[0] = 1;                       // left edge balloon
    for (int i = 0; i < n; i++) pad[i + 1] = nums[i];
    pad[n + 1] = 1;                   // right edge balloon
    int N = n + 2;

    int dp[64][64] = {{0}};

    for (int len = 2; len < N; len++) {          // range length
        for (int left = 0; left + len < N; left++) {
            int right = left + len;
            int best = 0;
            for (int k = left + 1; k < right; k++) {  // k burst last
                int coins = pad[left] * pad[k] * pad[right]
                          + dp[left][k] + dp[k][right];
                if (coins > best) best = coins;
            }
            dp[left][right] = best;
        }
    }
    return dp[0][N - 1];
}

int main(void) {
    int nums[] = {3, 1, 5, 8};
    printf("%d\n", maxCoins(nums, 4));
    return 0;
}

167

#include <iostream>
#include <vector>
using namespace std;

int maxCoins(vector<int>& nums) {
    int n = nums.size();
    vector<int> pad;
    pad.push_back(1);                         // left edge
    for (int x : nums) pad.push_back(x);
    pad.push_back(1);                         // right edge
    int N = pad.size();

    vector<vector<int>> dp(N, vector<int>(N, 0));

    for (int len = 2; len < N; len++) {       // range length
        for (int left = 0; left + len < N; left++) {
            int right = left + len;
            int best = 0;
            for (int k = left + 1; k < right; k++) {  // k burst last
                int coins = pad[left] * pad[k] * pad[right]
                          + dp[left][k] + dp[k][right];
                if (coins > best) best = coins;
            }
            dp[left][right] = best;
        }
    }
    return dp[0][N - 1];
}

int main() {
    vector<int> nums = {3, 1, 5, 8};
    cout << maxCoins(nums) << endl;
    return 0;
}

167

public class BurstBalloons {
    public static int maxCoins(int[] nums) {
        int n = nums.length;
        int[] pad = new int[n + 2];
        pad[0] = 1;                       // left edge
        pad[n + 1] = 1;                   // right edge
        for (int i = 0; i < n; i++) pad[i + 1] = nums[i];
        int N = n + 2;

        int[][] dp = new int[N][N];

        for (int len = 2; len < N; len++) {         // range length
            for (int left = 0; left + len < N; left++) {
                int right = left + len;
                int best = 0;
                for (int k = left + 1; k < right; k++) {  // k burst last
                    int coins = pad[left] * pad[k] * pad[right]
                              + dp[left][k] + dp[k][right];
                    if (coins > best) best = coins;
                }
                dp[left][right] = best;
            }
        }
        return dp[0][N - 1];
    }

    public static void main(String[] args) {
        int[] nums = { 3, 1, 5, 8 };
        System.out.println(maxCoins(nums));
    }
}

167

def max_coins(nums):
    pad = [1] + nums + [1]            # add edge balloons of value 1
    N = len(pad)
    dp = [[0] * N for _ in range(N)]  # dp[left][right] over the range

    for length in range(2, N):                 # range length
        for left in range(0, N - length):
            right = left + length
            best = 0
            for k in range(left + 1, right):   # k is burst last
                coins = (pad[left] * pad[k] * pad[right]
                         + dp[left][k] + dp[k][right])
                if coins > best:
                    best = coins
            dp[left][right] = best
    return dp[0][N - 1]


nums = [3, 1, 5, 8]
print(max_coins(nums))

167

function maxCoins(nums) {
  const pad = [1, ...nums, 1];        // add edge balloons of value 1
  const N = pad.length;
  const dp = Array.from({ length: N }, () => new Array(N).fill(0));

  for (let length = 2; length < N; length++) {   // range length
    for (let left = 0; left + length < N; left++) {
      const right = left + length;
      let best = 0;
      for (let k = left + 1; k < right; k++) {    // k is burst last
        const coins =
          pad[left] * pad[k] * pad[right] + dp[left][k] + dp[k][right];
        if (coins > best) best = coins;
      }
      dp[left][right] = best;
    }
  }
  return dp[0][N - 1];
}

const nums = [3, 1, 5, 8];
console.log(maxCoins(nums));

167

Let us walk through the Python version line by line. Code first, then why each line is there.

pad = [1] + nums + [1]
N = len(pad)
dp = [[0] * N for _ in range(N)]

We wrap the row with a 1 on each side. Those edge 1s are the imaginary balloons off the ends, so the coin formula never has to check for missing neighbors. Then we make an N by N table full of zeros. The cell dp[left][right] will hold the best coins for the balloons strictly between left and right.

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

We grow the ranges by length. We start at length = 2 because a range needs at least one balloon strictly inside it, and a gap of 2 between left and right leaves exactly one slot. Filling short ranges before long ones matters, because a long range reuses the answers of its shorter sub-ranges. right is just left plus the length.

best = 0
for k in range(left + 1, right):
    coins = (pad[left] * pad[k] * pad[right]
             + dp[left][k] + dp[k][right])
    if coins > best:
        best = coins

This inner loop is the heart of the trick. We try every balloon k inside the range as the last one to burst. Because k bursts last, the only balloons left beside it are left and right. So its coins are pad[left] * pad[k] * pad[right], fixed and clean. Then we add dp[left][k], the best from the sub-range to its left, and dp[k][right], the best from the sub-range to its right. We keep the largest total over all choices of k.

dp[left][right] = best
return dp[0][N - 1]

We store the best for this range. After all ranges are filled, dp[0][N-1] covers the full row from one edge to the other. That cell is the final answer, which is 167 for this input.

⏱️ Time and Space Complexity

Trying every order is factorial time, which is hopeless past a handful of balloons. The interval DP has three nested loops. One for range length, one for the left edge, and one for the last balloon k. That is O(n³) time, where n is the number of balloons. The table of ranges takes O(n²) space. For interview sizes O(n³) is perfectly fine, and it is a massive improvement over factorial.

🧩 Key Takeaways

• ✅ Ask which balloon bursts last in a range, not which bursts first.
• ✅ The last balloon’s neighbors are frozen at the range edges, so its coins are fixed.
• ✅ Pad the row with a 1 on each side so the coin math never hits a missing neighbor.
• ✅ Fill the table from short ranges to long ranges, because long ranges reuse short ones.
• ✅ Three nested loops give O(n³) time, far better than the factorial brute force.

🚀 What’s Next?

• Edit Distance
• Regular Expression Matching