Skip to main content

25. Burst Balloons

hardAsked at Chime

Maximize the coins you collect by bursting balloons in an optimal order, where the gain from a burst depends on its current neighbors.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given n balloons with numbers nums[i] on each, you burst all balloons. When you burst balloon i you gain nums[left] * nums[i] * nums[right] coins, where left and right are the adjacent balloons after previous bursts. Pad the ends with 1. Return the maximum coins you can collect.

Constraints

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

Examples

Example 1

Input
nums = [3,1,5,8]
Output
167

Example 2

Input
nums = [1,5]
Output
10

Approaches

1. Try every burst order

Recursively pick the next balloon to burst and recurse on the remaining set. Factorial blow-up without memoization.

Time
O(n!)
Space
O(n)
function best(arr) {
  if (arr.length === 0) return 0;
  let m = 0;
  for (let i = 0; i < arr.length; i++) {
    const L = i > 0 ? arr[i-1] : 1;
    const R = i < arr.length-1 ? arr[i+1] : 1;
    const rest = arr.slice(0,i).concat(arr.slice(i+1));
    m = Math.max(m, L * arr[i] * R + best(rest));
  }
  return m;
}

Tradeoff:

2. Interval DP on last balloon burst

Pad nums with 1s on both ends. Let dp[i][j] be the max coins from bursting all balloons strictly between i and j. Iterate over interval length and pick the last balloon k to burst inside (i,j): dp[i][j] = max over k of dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j].

Time
O(n^3)
Space
O(n^2)
function maxCoins(nums) {
  const a = [1, ...nums, 1];
  const n = a.length;
  const dp = Array.from({length: n}, () => new Array(n).fill(0));
  for (let len = 2; len < n; len++) {
    for (let i = 0; i + len < n; i++) {
      const j = i + len;
      for (let k = i + 1; k < j; k++) {
        const val = a[i] * a[k] * a[j] + dp[i][k] + dp[k][j];
        if (val > dp[i][j]) dp[i][j] = val;
      }
    }
  }
  return dp[0][n - 1];
}

Tradeoff:

Chime-specific tips

Chime asks burst-balloons-style interval DP when stress-testing your reasoning about non-greedy ordering of ACH retry batches where each batch's gain depends on its neighbors in time.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Burst Balloons and other Chime interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →