Burst Balloons

PracticeNeetCode ↗LeetCode ↗

Given n balloons with values nums, bursting balloon i earns nums[left] × nums[i] × nums[right] coins, where left and right are its current neighbors after previous bursts. Return the maximum coins obtainable by bursting every balloon.

Example

Key Pointers

• Thinking "which balloon do I burst first" makes the neighbors unpredictable; thinking "which balloon do I burst last within a range" makes the neighbors fixed — they're the range's boundaries, since everything else in between is already gone.
• Padding the array with a 1 on each end handles the out-of-bounds boundary case uniformly, without special-casing the first and last balloons.
• dp[l][r] represents the max coins from bursting everything strictly between indices l and r, trying every possible choice of which balloon in that range is burst last.

Step-by-Step Analysis

1. Pad nums with a 1 at both ends.
2. Create a 2D dp table, all zeros, sized to the padded array.
3. Process ranges by increasing length; for each range (l, r), try every k strictly between them as the last balloon burst in that range.
4. For that choice, the coins earned are nums[l] × nums[k] × nums[r], plus whatever was already earned bursting everything in (l, k) and (k, r) — take the best k.
5. The final answer sits at dp[0][n-1] of the padded array.

Complexity

Time: O(n³) — Space: O(n²)

Code

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

    for length in range(2, n):
        for l in range(n - length):
            r = l + length
            for k in range(l + 1, r):
                dp[l][r] = max(
                    dp[l][r],
                    dp[l][k] + balloons[l] * balloons[k] * balloons[r] + dp[k][r],
                )

    return dp[0][n - 1]

Code Explanation

How the solution above works, piece by piece.

1. Pad the array with 1 on both ends so every balloon always has two neighbours.
2. dp[l][r] = the most coins from bursting all balloons strictly between l and r (the ends stay).
3. Choose k as the last balloon burst in that range. At that moment only l and r are left beside it, so it earns balloons[l] * balloons[k] * balloons[r], and the left and right parts are independent: dp[l][k] + dp[k][r].
4. Fill by increasing range length so smaller ranges are ready first.
5. dp[0][n-1] is the answer. O(n³) time, O(n²) space.

Visual Walkthrough

Running it on nums = [3, 1, 5, 8]:

Video Explanation

NeetCode — Burst Balloons, LeetCode 312