Burst Balloons

The problem. Balloons in a row have numbers nums[i]. Bursting balloon i earns left · nums[i] · right, where left and right are its current neighbours (a missing neighbour counts as 1); then it's gone and its neighbours become adjacent. Burst them all. Return the most coins you can collect.

Example

nums = [3, 1, 5, 8]  ->  167   (burst 1, 5, 3, 8)
nums = [1, 5]        ->  10    (burst 1: 1*1*5, then 5: 1*5*1)
nums = [7]           ->  7

The idea: think about the last balloon, not the first

The obvious recursion picks the first balloon to burst. But then its two neighbours become adjacent, so the left part and the right part are no longer separate problems — the state would have to be the whole set of balloons left, 2ⁿ of them.

Flip it: pick the balloon k that bursts last in a range. While k is still standing, it separates the balloons on its left from those on its right — they never become neighbours, so the two sides really are independent. And when k finally bursts, everything between l and r is gone, so its neighbours are exactly l and r. Pad the row with a 1 at each end, and let best(l, r) be the most coins from bursting every balloon strictly between l and r:

best(l, r) = max over l < k < r of   best(l, k) + vals[l] * vals[k] * vals[r] + best(k, r)
best(l, r) = 0 when nothing is between them (r - l < 2)

This is the hardest kind of interval DP: instead of shrinking from the ends, it tries every split point inside the range.

1. Memoized recursion

1function maxCoins(nums) {2  const vals = [1, ...nums, 1];                  // a 1 at each end: bursting next to a wall3  const memo = new Map();4  const best = (l, r) => {                       // most coins for the balloons strictly between l and r5    if (r - l < 2) return 0;                     // nothing between them6    const key = l * vals.length + r;7    if (memo.has(key)) return memo.get(key);8    let most = 0;9    for (let k = l + 1; k < r; k++) {            // k is the LAST balloon burst between l and r10      most = Math.max(most, best(l, k) + vals[l] * vals[k] * vals[r] + best(k, r));11    }12    memo.set(key, most);13    return most;14  };15  return best(0, vals.length - 1);16}

Time O(n³), space O(n²). There are O(n²) ranges and each tries O(n) last balloons. The recursion is only O(n) deep, since every call shrinks the range.

2. Bottom-up, shortest ranges first

1function maxCoins(nums) {2  const vals = [1, ...nums, 1];3  const m = vals.length;4  // dp[l][r]: most coins for bursting every balloon strictly between l and r5  const dp = Array.from({ length: m }, () => new Array(m).fill(0));6  for (let gap = 2; gap < m; gap++) {            // shorter ranges first7    for (let l = 0; l + gap < m; l++) {8      const r = l + gap;9      for (let k = l + 1; k < r; k++) {          // k bursts last, between l and r10        dp[l][r] = Math.max(dp[l][r], dp[l][k] + vals[l] * vals[k] * vals[r] + dp[k][r]);11      }12    }13  }14  return dp[0][m - 1];15}

Time O(n³), space O(n²). Every dp[l][k] and dp[k][r] covers a shorter range than dp[l][r], so filling by increasing gap guarantees they're ready. With LeetCode's n ≤ 300 that's about 4.5 million steps — fast.

Comparing the approaches

The brute force — try every burst order — is O(n!), and choosing the first balloon gives no clean subproblems. The whole problem is the insight that the last balloon splits the range cleanly; say that first, and the code follows.

Edge cases to test

Variations