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 Sam K., 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

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →