Burst Balloons — Solution

Problem

You have a row of balloons, each labeled with a positive integer. When you burst a balloon, you earn coins equal to its label multiplied by its left neighbor's label and its right neighbor's label; out-of-bounds neighbors count as 1. Burst every balloon in whatever order maximizes total coins.

• Input: nums = [3, 1, 4, 2]
• Output: 45
• Explanation: Burst in order 1 → 4 → 2 → 3, collecting 3×1×4=12, then 3×4×2=24, then 3×2×1=6, then 1×3×1=3 for 45 total.

A smaller example: bursting the middle balloon in [3, 1, 4] first (earning 3×1×4=12), then the left (1×3×4=12), then the last (1×4×1=4) gives 28 — the best possible ordering for that input.

Intuition

The naive instinct is to ask "which balloon should I burst first?" but this breaks DP: after you burst balloon A, the neighbors of every adjacent balloon change, so subproblems are not independent. Flip the question: ask "which balloon should I burst last within a given range?" When a balloon is the last one standing between two fixed boundaries, both neighbors are known constants, making the coin formula deterministic. This "last burst" framing converts the problem into a clean interval DP.

Approach 1 — Brute Force

Try every possible first balloon to burst, recurse on what's left, and take the max.

1. If no balloons remain, return 0.
2. For each balloon at index i, determine its current left and right neighbors (or 1 at the boundaries).
3. Calculate the coins earned from bursting i.
4. Remove i from the list and recurse on the remainder.
5. Restore i and move to the next choice.
6. Return the maximum total found.

1def maxCoins(nums: list[int]) -> int:
2    def burst(balloons: list[int]) -> int:
3        if not balloons:
4            return 0
5        best = 0
6        for i in range(len(balloons)):
7            left_val = balloons[i - 1] if i > 0 else 1
8            right_val = balloons[i + 1] if i < len(balloons) - 1 else 1
9            coins = left_val * balloons[i] * right_val
10            remaining = balloons[:i] + balloons[i + 1:]
11            best = max(best, coins + burst(remaining))
12        return best
13    return burst(nums)

Time: O(n · n!) — every ordering of n balloons is explored, and each level copies or shifts the array in O(n).
Space: O(n) — maximum call stack depth is n.

Approach 2 — Dynamic Programming (Interval DP)

Pad the array with sentinel 1s at both ends. Define dp[left][right] as the maximum coins from bursting every balloon strictly between indices left and right (open interval). For each such range, try every k as the last balloon burst — when k is last, its neighbors are exactly padded[left] and padded[right].

1. Build padded = [1] + nums + [1], length n.
2. Initialize all dp[i][j] = 0.
3. Loop over window lengths from 2 up to n - 1 (smallest intervals first).
4. For each (left, right) pair of that length, loop k from left + 1 to right - 1.
5. Update: dp[left][right] = max(dp[left][right], dp[left][k] + padded[left]*padded[k]*padded[right] + dp[k][right]).
6. Return dp[0][n - 1].

1def maxCoins(nums: list[int]) -> int:
2    padded = [1] + nums + [1]
3    n = len(padded)
4    dp = [[0] * n for _ in range(n)]
5
6    for length in range(2, n):                  # grow from smallest intervals outward
7        for left in range(n - length):
8            right = left + length
9            for k in range(left + 1, right):    # k is the last burst in (left, right)
10                coins = padded[left] * padded[k] * padded[right]
11                dp[left][right] = max(
12                    dp[left][right],
13                    dp[left][k] + coins + dp[k][right]
14                )
15
16    return dp[0][n - 1]

Time: O(n³) — O(n²) intervals, each requiring an O(n) loop over k.
Space: O(n²) for the DP table; the padded array adds O(n).

Complexity Summary

Common Mistakes

• Thinking "first burst" instead of "last burst" — the first-burst direction breaks DP independence because bursting one balloon changes who the neighbors of adjacent balloons are. Last-burst fixes both boundary values, making subproblems self-contained.
• Forgetting sentinel 1s — without padding, boundary conditions require special-casing everywhere in the loop; adding 1 at both ends lets the formula padded[left]*padded[k]*padded[right] apply uniformly including at array edges.
• Wrong loop order in bottom-up DP — smaller intervals must be computed before larger ones. Processing dp[0][5] before dp[1][4] reads zero instead of the correct subresult.
• Off-by-one on the inner k loop — k ranges over the open interval (left, right), meaning k must satisfy left < k < right. Writing k <= right or k < right - 1 misses valid candidates or reads a boundary sentinel as a real balloon.
• Confusing padded vs original indices — padded[0] and padded[n-1] are sentinels, not real balloons. The actual balloons occupy padded[1] through padded[n-2], and the answer is always dp[0][n-1] in the padded coordinate system.

Related Problems

• Unique Binary Search Trees — interval DP where you pick which value becomes the root of each subrange, the same "choose what's last/central" framing
• Longest Palindromic Subsequence — interval DP that expands outward from smaller substrings, building answers bottom-up by window length
• Edit Distance — classic 2D DP where every dp[i][j] depends on strictly smaller subproblems, same bottom-up filling discipline
• Palindrome Partitioning — partition DP that similarly iterates over all ways to divide a range and combines sub-results