Burst Balloons — Interval DP with Reverse Thinking (The Hardest Grid DP Pattern)

Problem Statement#

You are given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons. If you burst the i-th balloon, you will get nums[i-1] * nums[i] * nums[i+1] coins. If i-1 or i+1 goes out of the array bounds, treat it as if there is a balloon with value 1 painted on it. Return the maximum coins you can collect by bursting the balloons wisely.

Constraints:

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

Example 1:

Input:  nums = [3, 1, 5, 8]
Output: 167
Explanation:
  nums = [3, 1, 5, 8] → burst 1 → [3, 5, 8] coins = 3*1*5 = 15
  nums = [3, 5, 8]    → burst 5 → [3, 8]    coins = 3*5*8 = 120
  nums = [3, 8]       → burst 3 → [8]        coins = 1*3*8 = 24
  nums = [8]          → burst 8 → []          coins = 1*8*1 = 8
  Total: 15 + 120 + 24 + 8 = 167

Example 2:

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

Example 3:

Input:  nums = [5]
Output: 5

Why This Problem Matters#

Burst Balloons is one of the hardest standard DP problems in FAANG interviews. It is a benchmark for interval DP — a pattern where dp[i][j] represents the optimal result for a subproblem on a contiguous interval [i, j]. Other interval DP problems include Minimum Cost to Merge Stones, Palindrome Partitioning II, and Matrix Chain Multiplication.

What makes Burst Balloons notoriously difficult is the coupling problem: when you burst balloon k in interval [i, j], its neighbors change. Trying to enumerate "which balloon to burst first" creates dependencies between subproblems that make the recurrence ill-defined.

The breakthrough insight — think about which balloon is burst LAST instead of first — eliminates this coupling entirely. When balloon k is burst last in interval (i, j), its neighbors are always exactly the boundaries nums[i] and nums[j], which are fixed. This simple reversal transforms an unsolvable greedy problem into a clean O(n^3) DP.

Google, Amazon, and Meta ask this problem to test whether candidates can find non-obvious problem reformulations, not just apply standard DP templates.

The Core Insight#

Augment the array: Add virtual balloons with value 1 at both ends. So nums' = [1] + nums + [1]. This makes the boundary coins well-defined without special-casing.

State definition: dp[i][j] = maximum coins obtainable by bursting all balloons strictly between index i and index j in the augmented array (i and j themselves are NOT burst).

Key reversal: Instead of asking "which balloon do we burst first?", ask: "which balloon k is the last to be burst in the open interval (i, j)?"

Why this works: When k is burst last, all other balloons in (i, j) are already gone. The neighbors of k at the moment of its burst are exactly nums'[i] and nums'[j] — fixed boundaries, no coupling!

Recurrence:

dp[i][j] = max over all k in (i, j):
    dp[i][k] + dp[k][j] + nums'[i] * nums'[k] * nums'[j]

• dp[i][k]: optimal coins from bursting everything in (i, k) before k
• dp[k][j]: optimal coins from bursting everything in (k, j) before k
• nums'[i] * nums'[k] * nums'[j]: coins from bursting k last (neighbors are i and j)

Answer: dp[0][n+1] (burst everything between the two sentinel balloons)

Iteration order: Intervals must be filled in increasing length (size 2, 3, ... n+1) to ensure subproblems are solved before they are needed.

Building the DP Solution#

Step 1 — Augment and define:

def maxCoins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    # dp[i][j] = max coins from bursting all in open interval (i, j)

Step 2 — Fill by interval length:

    # length = number of balloons in the open interval (i, j)
    for length in range(2, n):  # smallest interval: length 2 means 0 balloons inside
        for i in range(0, n - length):
            j = i + length
            for k in range(i + 1, j):  # k is the last balloon burst in (i, j)
                coins = nums[i] * nums[k] * nums[j]
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + coins)
    return dp[0][n - 1]

Visual Dry Run#

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

Augmented: nums' = [1, 3, 1, 5, 8, 1] (indices 0-5)

We want dp[0][5]. Build intervals bottom-up:

Length 2 (no interior balloons): All dp[i][i+2] intervals with exactly one balloon inside:

Length 3 (two balloons inside):

Length 4 (three balloons inside):

Length 5 (all 4 original balloons):

dp[0][5]: k=1: 0+159+131=162; k=2: 3+45+111=49; k=3: 30+40+151=75; k=4: 159+0+181=167

dp[0][5] = 167 — matches expected output.

Optimized Solution#

Python#

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        # Add sentinel balloons with value 1 at both ends
        nums = [1] + nums + [1]
        n = len(nums)
 
        # dp[i][j] = max coins from open interval (i, j)
        dp = [[0] * n for _ in range(n)]
 
        # Fill by increasing interval length
        # length is the gap between i and j (j = i + length)
        for length in range(2, n):
            for i in range(n - length):
                j = i + length
                # Try every balloon k as the last to burst in (i, j)
                for k in range(i + 1, j):
                    coins = nums[i] * nums[k] * nums[j]
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + coins)
 
        return dp[0][n - 1]

JavaScript#

var maxCoins = function(nums) {
    // Add sentinels
    nums = [1, ...nums, 1];
    const n = nums.length;
 
    // dp[i][j] = max coins bursting all balloons in open interval (i, j)
    const dp = Array.from({length: n}, () => new Array(n).fill(0));
 
    for (let length = 2; length < n; length++) {
        for (let i = 0; i <= n - length - 1; i++) {
            const j = i + length;
            for (let k = i + 1; k < j; k++) {
                const coins = nums[i] * nums[k] * nums[j];
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + coins);
            }
        }
    }
 
    return dp[0][n - 1];
};

Complexity Analysis#

For n = 300 (max constraint), this is 27 million operations — well within time limits.

Common Mistakes#

1. Trying to enumerate "first balloon to burst" instead of "last balloon to burst." The first-burst approach creates coupled subproblems: after bursting balloon k first, its neighbors change and the subproblems for the left and right halves are entangled. The problem becomes unsolvable with clean DP. Always think "last balloon."

2. Forgetting to add sentinel balloons. Without adding 1s at both ends, boundary balloons have undefined neighbors. The augmentation makes every balloon burst "internal" to the array, and the boundary coins are cleanly defined as nums'[i] * nums'[k] * nums'[j].

3. Incorrect interval ordering. The outer loop must iterate by increasing interval length. If you iterate by i and j in any other order, you may use dp[i][k] before it has been computed. Length-based iteration guarantees all smaller intervals are ready.

4. Including i or j themselves in the burst. dp[i][j] represents coins from bursting balloons strictly between i and j. The loop for k in range(i+1, j) correctly excludes i and j. Using range(i, j+1) or range(i+1, j+1) breaks this invariant.

5. Conflating the "k is last burst" insight with the formula. When k is the last balloon burst in (i, j), all other balloons in (i, j) are already gone. Therefore the neighbors at the moment k is burst are nums'[i] and nums'[j] — not nums'[k-1] and nums'[k+1] (which would be wrong because those balloons may already be burst).

Interview Tips#

• Open with the key insight: "The trick is to think about which balloon is burst last in an interval, not first. When a balloon is burst last, its neighbors are the fixed interval boundaries — no coupling."
• Add sentinels before writing any code: "I'll pad the array with 1s at both ends to handle boundary cases cleanly."
• State the DP semantics precisely: "dp[i][j] = max coins from bursting all balloons strictly between index i and j."
• Explain the loop order: "I iterate by increasing interval length because smaller subproblems must be solved before larger ones."
• If asked about time complexity: "O(n^3) — n^2 intervals times n choices per interval. For n=300, that's 27 million operations, which is fast enough."

Follow-up Questions#

Q: Can this be solved with greedy or divide-and-conquer? Greedy fails because the optimal local choice (burst the smallest balloon first) is not globally optimal — neighbors change after each burst and the global optimum depends on the order. Divide-and-conquer without memoization is exponential. Interval DP with the "last burst" insight is the canonical optimal approach.

Q: How would you reconstruct the optimal bursting order? Maintain a parent[i][j] table recording which k was chosen at each interval. Recursively recover: reconstruct(0, n-1) gives k for the outermost interval, then recurse on (0, k) and (k, n-1).

Q: What if balloon values change dynamically? Recompute the DP table — it is O(n^3) per update. For frequently updated arrays, more sophisticated range-tree approaches exist but are beyond standard interview scope.

Q: How does this relate to Matrix Chain Multiplication? Matrix Chain Multiplication is also interval DP: dp[i][j] = min cost to multiply matrices from i to j. The optimal split point k is chosen last (or equivalently, the outermost multiplication). The structure is identical — both are "choose split last" interval DP.

Key Takeaways#

• The fundamental insight: think about which balloon is burst last in each interval, not first. Last-burst means neighbors are the fixed interval boundaries — subproblems decouple cleanly.
• Add sentinels [1] + nums + [1] before building the DP table.
• dp[i][j] = max over k in (i,j): dp[i][k] + dp[k][j] + nums'[i] * nums'[k] * nums'[j]
• Fill the table by increasing interval length — smaller intervals must be computed before larger ones.
• O(n^3) time, O(n^2) space — optimal for this problem.
• Burst Balloons is the canonical interval DP problem. Mastering it makes Matrix Chain Multiplication, Minimum Cost to Merge Stones, and Strange Printer tractable.
• Google, Amazon, and Meta ask this to test whether candidates can find non-obvious problem reformulations — not just apply templates.