Skip to content
AI360Xpert
Beta
Back to 2-D Dynamic Programming
Difficulty: Hard2-D Dynamic Programming

Burst Balloons

Problem in Plain English

Bursting a balloon pays the product of its number with its two live neighbours, where missing neighbours count as 1. Choose the burst order that collects the most coins across all balloons.

Problem Statement

You are given n balloons with numbers in the array nums. Bursting balloon i pays nums[i - 1] * nums[i] * nums[i + 1] coins, where a neighbour outside the array counts as 1, and the neighbours close ranks after each burst.

Burst the balloons one by one in any order until none remain. The coins from each burst add up to a total that depends entirely on the chosen order.

Return the maximum total coins achievable over every possible burst order.

Constraints

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

Examples

Example 1

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

Burst in the order 1, 5, 3, 8 for 15 + 120 + 24 + 8 = 167.

Example 2

Input
nums = [1, 5]
Output
10

Burst 1 first for 5, then 5 for 5, totalling 10.

Example 3

Input
nums = [7]
Output
7

The only balloon has missing neighbours on both sides, each counted as 1. Its forced payout is 1 * 7 * 1 = 7.

Example 4

Input
nums = [0, 5, 0]
Output
5

Burst the two zeroes first, earning 0 each, then burst 5 between the outside ones for 5. Bursting 5 while both zeroes remain earns 0 and leaves only zeroes, losing all 5 coins.

Intuition

Removing a balloon changes which values are neighbours, so a locally large payout need not produce the largest total. On [3, 1, 5, 8], removing 1 first preserves 3 and 8 around 5 for a later payout of 120. Think backwards: if 8 is the last balloon, all earlier work happens between fixed outside boundaries of 1. The same idea applies inside any smaller interval.

Approaches

Try Every Burst Order

Solution Details

Reveal Try Every Burst Order: intuition, complexity, and code

Hints

Hint 1
Bursting first is messy because the neighbours fuse; ask instead which balloon bursts last inside a section.
Hint 2
The last balloon of an interval always faces the two fixed boundary values, so its coins are known and the two sides separate cleanly.
Hint 3
Pad the array with 1 on both ends and fill the table from short intervals to long ones, trying every candidate for last.

Edge Cases

  • A single balloon such as nums = [7], which pays 1 * 7 * 1 = 7.
  • Zeroes such as nums = [0, 5], where bursting the 0 first still pays 0 but unlocks the better neighbour pairing.
  • Two balloons such as nums = [1, 5], where bursting the 1 first (10) beats bursting the 5 first (6).
  • Duplicate values still occupy different positions; restore the removed index rather than searching by value. All-zero arrays score 0, while every balloon must still be removed.

Common Mistakes and Interview Tips

  • Splitting independent left and right subproblems around the first burst is invalid: its removal fuses neighbours across the split. First-burst search is correct only when it tracks the entire live list, as the exhaustive approach does.
  • Forgetting the 1 padding and special-casing the array edges instead, which drops boundary coins.
  • Filling long intervals before the short ones they read, which uses still-empty table cells.
  • Choosing the largest immediate neighbour product greedily misses later payouts. In an interview, explain which balloons stay alive as interval boundaries and why the last burst separates independent subproblems.

Key Takeaway

When removing an element fuses its neighbours, think backwards: fixing the last removal splits the range into independent halves made for interval DP.