Burst balloons

Busting each balloon gives product of its neighbors and itself return sum of highest coins returned

Burst Balloons

Problem

You have n balloons, numbered from 0 to n - 1. Each balloon has a number painted on it. The numbers are given in an array nums.

You must burst all the balloons. When you burst balloon i, you get this many coins:

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

If i - 1 or i + 1 is outside the array, treat it as a balloon with the number 1.

Return the maximum coins you can collect by bursting the balloons in the best order.

Examples

Example 1

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

• [3, 1, 5, 8] -> burst 1 -> [3, 5, 8] and get 3 * 1 * 5 = 15
• [3, 5, 8] -> burst 5 -> [3, 8] and get 3 * 5 * 8 = 120
• [3, 8] -> burst 3 -> [8] and get 1 * 3 * 8 = 24
• [8] -> burst 8 -> [] and get 1 * 8 * 1 = 8
• Total coins = 15 + 120 + 24 + 8 = 167

Example 2

Input: nums = [1, 2, 3, 4]
Output: 40

• [1, 2, 3, 4] -> burst 3 -> [1, 2, 4] and get 2 * 3 * 4 = 24
• [1, 2, 4] -> burst 2 -> [1, 4] and get 1 * 2 * 4 = 8
• [1, 4] -> burst 1 -> [4] and get 1 * 1 * 4 = 4
• [4] -> burst 4 -> [] and get 1 * 4 * 1 = 4
• Total coins = 24 + 8 + 4 + 4 = 40

Main Idea

This is a Partition DP problem. It is similar to Matrix Chain Multiplication.

Why the "first burst" idea does not work

Let us say we try to choose the first balloon to burst in a range.

• When a balloon bursts, its left and right neighbors become new neighbors.
• So the left side and the right side are not independent anymore.
• The coins of one side depend on what happens on the other side.

This makes the problem very hard to split into small parts.

The reverse idea: choose the last balloon

Instead, we think in reverse. We ask: which balloon will be burst last in this range?

Let us say balloon k is the last one to burst in the range [i, j].

• All other balloons in [i, j] are already burst before k.
• So when k bursts, its neighbors are the balloons just outside the range. These are balloons[i - 1] and balloons[j + 1].
• The coins for k are balloons[i - 1] * balloons[k] * balloons[j + 1].
• The left part [i, k - 1] and the right part [k + 1, j] are now independent. Balloon k is still standing between them, like a wall, until the end.

So the formula is:

coins = balloons[i - 1] * balloons[k] * balloons[j + 1] + dp[i][k - 1] + dp[k + 1][j]

We try every k from i to j and keep the maximum.

Padding the array

Balloons at the edges need a neighbor of 1. So we add a 1 at the start and at the end of the array.

nums     = [3, 1, 5, 8]
balloons = [1, 3, 1, 5, 8, 1]

Now the real balloons are at indexes 1 to n. The two padded 1s are at index 0 and index n + 1. We never burst them.

The DP state

dp[i][j] means: the maximum coins we can get by bursting all balloons from index i to j, when the balloons at i - 1 and j + 1 are still there.

Base Case

• If i > j, the range is empty. There is nothing to burst, so the answer is 0.

Solution 1: Recursion + Memoization (Top-Down)

This version is easy to understand. We write a recursive function and save every answer, so we never solve the same range twice.

function maxCoins(nums) {
    const n = nums.length;

    // Pad the array with 1 at both ends
    const balloons = [1, ...nums, 1];

    // -1 means "not solved yet"
    const dp = Array.from({ length: n + 2 }, () => Array(n + 2).fill(-1));

    function solve(i, j) {
        // empty range, no coins
        if (i > j) return 0;

        // answer is already saved
        if (dp[i][j] !== -1) return dp[i][j];

        let maxi = 0;

        // try every balloon k as the LAST one to burst in [i, j]
        for (let k = i; k <= j; k++) {
            let coins =
                balloons[i - 1] * balloons[k] * balloons[j + 1] +
                solve(i, k - 1) +
                solve(k + 1, j);

            maxi = Math.max(maxi, coins);
        }

        return (dp[i][j] = maxi);
    }

    // all real balloons are in the range [1, n]
    return solve(1, n);
}

Complexity

• Time Complexity: O(n³)
  • There are about n * n states (i, j).
  • Each state is solved once, and runs a loop over k that takes up to O(n).
• Space Complexity: O(n²)
  • The dp table has (n + 2) * (n + 2) cells.
  • The recursion stack uses O(n) extra space.

Solution 2: Tabulation (Bottom-Up)

In this method, we do not use recursion. We solve small ranges first, then use them to solve bigger ranges.

function maxCoins(nums) {
    const n = nums.length;

    // Pad the array with 1 at both ends
    const balloons = [1, ...nums, 1];
    const size = balloons.length;

    // DP table initialized to 0
    const dp = Array.from({ length: size }, () => Array(size).fill(0));

    // Range length from 1 to n
    for (let len = 1; len <= n; len++) {
        for (let i = 1; i <= n - len + 1; i++) {
            let j = i + len - 1;

            // Try every balloon in [i, j] as the last one to burst
            for (let k = i; k <= j; k++) {
                let coins = balloons[i - 1] * balloons[k] * balloons[j + 1];
                let remaining = dp[i][k - 1] + dp[k + 1][j];

                dp[i][j] = Math.max(dp[i][j], coins + remaining);
            }
        }
    }

    return dp[1][n];
}

How the Tabulation Code Works

Let us go through the code step by step.

Step 1: Pad the array

• balloons = [1, ...nums, 1] adds a 1 on both sides.
• Now the real balloons are at indexes 1 to n.
• size is n + 2.

Step 2: Create the dp table

• The table has size * size cells, and all values start at 0.
• A value of 0 is a good start, because an empty range gives 0 coins.
• We need cells like dp[i][i - 1] (when k = i) and dp[j + 1][j] (when k = j). These are empty ranges, and they stay 0. That is why the padded size is important.

Step 3: Loop over the range length

• len goes from 1 to n.
• We start with ranges of one balloon, then two balloons, and so on.
• This order is important. When we solve a range of length len, all smaller ranges are already solved.

Step 4: Loop over the start of the range

• i is the start of the range.
• j = i + len - 1 is the end of the range.
• The loop runs while i <= n - len + 1, so j never goes past n.

Step 5: Try every balloon as the last one

• k goes from i to j.
• coins = balloons[i - 1] * balloons[k] * balloons[j + 1] is what we get when k bursts last. Its neighbors are the balloons just outside the range.
• remaining = dp[i][k - 1] + dp[k + 1][j] is the best result of the left part and the right part.
• We save the maximum in dp[i][j].

Step 6: Return the answer

• dp[1][n] is the best result for all real balloons.

Dry Run

Let us take nums = [3, 1, 5].

The padded array is balloons = [1, 3, 1, 5, 1]. Here n = 3.

Length 1 (one balloon in the range):

• dp[1][1]: 1 * 3 * 1 = 3
• dp[2][2]: 3 * 1 * 5 = 15
• dp[3][3]: 1 * 5 * 1 = 5

Length 2 (two balloons in the range):

• dp[1][2] (balloons 3 and 1, outside neighbors 1 and 5):
  • Last is k = 1: 1 * 3 * 5 = 15, plus dp[2][2] = 15. Total = 30.
  • Last is k = 2: 1 * 1 * 5 = 5, plus dp[1][1] = 3. Total = 8.
  • Best = 30.
• dp[2][3] (balloons 1 and 5, outside neighbors 3 and 1):
  • Last is k = 2: 3 * 1 * 1 = 3, plus dp[3][3] = 5. Total = 8.
  • Last is k = 3: 3 * 5 * 1 = 15, plus dp[2][2] = 15. Total = 30.
  • Best = 30.

Length 3 (all balloons, outside neighbors 1 and 1):

• Last is k = 1: 1 * 3 * 1 = 3, plus dp[2][3] = 30. Total = 33.
• Last is k = 2: 1 * 1 * 1 = 1, plus dp[1][1] + dp[3][3] = 3 + 5. Total = 9.
• Last is k = 3: 1 * 5 * 1 = 5, plus dp[1][2] = 30. Total = 35.
• Best = 35.

The answer is dp[1][3] = 35.

This means the best plan is: burst 1, then 3, and burst 5 last.

Complexity

• Time Complexity: O(n³)
  • We use three loops: len, i and k.
  • Each loop runs up to n times.
• Space Complexity: O(n²)
  • The dp table has (n + 2) * (n + 2) cells.
  • There is no recursion stack.

Comparison

Summary

• This is a Partition DP problem, like Matrix Chain Multiplication.
• Thinking about the first balloon to burst does not work. The left and right sides depend on each other.
• Thinking about the last balloon to burst works. The left and right sides become independent.
• We add a 1 at both ends of the array to handle the edges.
• dp[i][j] is the maximum coins from bursting all balloons in the range [i, j].
• The formula is balloons[i - 1] * balloons[k] * balloons[j + 1] + dp[i][k - 1] + dp[k + 1][j].
• In tabulation, we solve small ranges first, so bigger ranges can use their results.
• Both solutions run in O(n³) time and use O(n²) space.