Skip to main content

312. Burst Balloons

hard

Maximize coins by bursting balloons one at a time, where each burst yields the product of its neighbors. The textbook trick: invert the question — think of which balloon is burst LAST in each interval — and interval DP falls out.

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

Problem

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 ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 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

Examples

Example 1

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

Explanation: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []. coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167.

Example 2

Input
nums = [1,5]
Output
10

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Reasoning about which balloon to burst FIRST is hard because the array keeps changing. Flip the question: which balloon is burst LAST in a given interval?

Hint 2

Pad nums with 1s at both ends. Define dp[i][j] = max coins collectible by bursting all balloons strictly between i and j.

Hint 3

If k is the last balloon burst in (i, j), it contributes nums[i] * nums[k] * nums[j] (its neighbors at burst time are i and j, since everything else is already gone).

Hint 4

dp[i][j] = max over k in (i, j) of dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]. Fill in increasing interval length.

Solution approach

Reveal approach

Interval DP with a 'last to burst' inversion. Pad nums with 1 at both ends so the array becomes nums' of length n + 2. Define dp[i][j] as the maximum coins obtainable by bursting every balloon strictly between positions i and j of nums'. For each interval length from 2 to n + 1 and each (i, j), try every k in (i, j) as the last balloon to burst inside (i, j). When k is the last to go, its neighbors at burst time are exactly i and j — every other balloon in the interval is already gone. So dp[i][j] = max over k of dp[i][k] + dp[k][j] + nums'[i] * nums'[k] * nums'[j]. Return dp[0][n+1]. The padding handles edge balloons cleanly.

Complexity

Time
O(n^3)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • interval-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta

Practice these live with InterviewChamp.AI

Drill Burst Balloons and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →