Burst Balloons

Difficulty: Hard Source: NeetCode

Problem

You are given n balloons, indexed from 0 to n-1. Each balloon has a number nums[i]. If you burst balloon i, you gain nums[i-1] * nums[i] * nums[i+1] coins. The balloons at the boundaries use 1 for out-of-bound indices. Find the maximum coins you can collect by bursting all the balloons.

Example 1: Input: nums = [3, 1, 5, 8] Output: 167 Explanation: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167

Example 2: Input: nums = [1, 5] Output: 10

Constraints:

• 1 <= nums.length <= 300
• 0 <= nums[i] <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

• Interval DP — solving problems defined over subarrays
• Thinking in reverse — choosing which element to process last instead of first

1. Brute Force / Recursive

Intuition

Naively, try every permutation of bursting order. At each step, choose any balloon to burst, collect coins, recurse on what’s left. This is O(n!) — too slow. The reason is that bursting a balloon changes the neighbours of remaining balloons, making subproblems entangle.

Solution

def maxCoins(nums):
    nums = [1] + nums + [1]  # add boundary sentinels

    def dfs(balloons):
        if not balloons:
            return 0
        best = 0
        for i, b in enumerate(balloons):
            left = balloons[i - 1] if i > 0 else 1
            right = balloons[i + 1] if i < len(balloons) - 1 else 1
            coins = left * b * right
            remaining = balloons[:i] + balloons[i + 1:]
            best = max(best, coins + dfs(remaining))
        return best

    return dfs(nums[1:-1])  # don't burst the sentinels


# Warning: This is O(n!) — only works for tiny inputs
print(maxCoins([3, 1, 5, 8]))  # 167
print(maxCoins([1, 5]))        # 10

Complexity

• Time: O(n!) — factorial, unusable for large inputs
• Space: O(n) — recursion depth

2. Interval DP — Think in Reverse

Intuition

The trick: instead of thinking about which balloon to burst first, think about which balloon to burst last within an interval (i, j). If balloon k is the last one burst in (i, j), its neighbours at that moment are the sentinels nums[i] and nums[j] (the boundaries of the interval). Everything between i and k, and between k and j, was already burst.

So: dp[i][j] = max over k in (i,j) of: dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j].

We pad nums with 1s on both ends as sentinels. The answer is dp[0][n+1].

Algorithm

1. Pad nums with sentinels: nums = [1] + nums + [1], length n+2.
2. Create dp table of size (n+2) x (n+2).
3. Fill by increasing interval length (from 2 upward).
4. For each interval (i, j), try each k in (i, j) as the last balloon burst.
5. dp[i][j] = max(dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j]).
6. Return dp[0][n+1].

Solution

def maxCoins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    # Interval length from 2 (at least one balloon inside)
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            for k in range(i + 1, j):
                coins = nums[i] * nums[k] * nums[j]
                dp[i][j] = max(dp[i][j], dp[i][k] + coins + dp[k][j])

    return dp[0][n - 1]


print(maxCoins([3, 1, 5, 8]))  # 167
print(maxCoins([1, 5]))        # 10
print(maxCoins([5]))           # 5


# Top-down memoization version
from functools import lru_cache

def maxCoins_memo(nums):
    nums = [1] + nums + [1]
    n = len(nums)

    @lru_cache(maxsize=None)
    def dfs(i, j):
        if j - i < 2:
            return 0
        best = 0
        for k in range(i + 1, j):
            coins = nums[i] * nums[k] * nums[j]
            best = max(best, dfs(i, k) + coins + dfs(k, j))
        return best

    return dfs(0, n - 1)


print(maxCoins_memo([3, 1, 5, 8]))  # 167
print(maxCoins_memo([1, 5]))        # 10

Complexity

• Time: O(n³) — three nested loops/dimensions
• Space: O(n²) — dp table

Common Pitfalls

Thinking about which balloon to burst first. This is the wrong framing — it entangles subproblems because bursting a balloon changes its neighbours. The “last burst” framing keeps intervals independent.

Not padding with sentinels. The boundary condition (1 outside the array) must be represented explicitly. Padding nums with [1, ...original..., 1] makes the interval DP formula clean.

Interval endpoints are exclusive. In dp[i][j], we burst all balloons strictly between i and j. Balloons i and j are the boundaries (already burst or sentinels), not included in the current subproblem.