Burst Balloons
A row of balloons is given as nums, where nums[i] is the number on balloon i. You burst all of them, one at a time, in any order. Bursting a balloon earns left × nums[i] × right coins, where left and right are the numbers on its current neighbours, the nearest balloons on each side still in the row. A missing neighbour counts as 1. After a burst, its two neighbours become adjacent. Return the most coins you can collect.
Function
- numsinteger-array
- the numbers on the balloons, from left to right
- Returnsinteger
- the most coins you can collect by bursting every balloon
Constraints
1 ≤ nums.length ≤ 3000 ≤ nums[i] ≤ 100- The answer is below 3 × 108, so it fits in a 32-bit signed integer.
Examples
- Input
- nums = [2, 4, 3]
- Output
- 33
- Explanation
- Burst the 4 for 2 × 4 × 3 = 24. The 2, now next to the 3, earns 1 × 2 × 3 = 6, and the 3 earns 3: 33 in all.
- Input
- nums = [6, 1, 2, 5]
- Output
- 108
- Explanation
- Burst the 1 (6 × 1 × 2 = 12), then the 2, now between 6 and 5 (6 × 2 × 5 = 60), then the 5 for 30 and the 6 for 6: 108 in all.
- Input
- nums = [8]
- Output
- 8
- Explanation
- The only balloon has no neighbours, and each missing neighbour counts as 1, so it earns 1 × 8 × 1 = 8.
Follow-up
Can you also return one bursting order that earns the most coins?
Hints
Open them one at a time. Each one gives away a little more.
Suppose you decide which balloon to burst first. Its two neighbours become adjacent, so the balloons on its left and the balloons on its right still affect each other. Can you split the problem into two smaller ones that way?
Turn the question around and pick the balloon that bursts last in a stretch. Until then it stands still, like a wall, so the balloons on its left and on its right never become neighbours. When it finally bursts, its neighbours are the two balloons that border the stretch.
Put a 1 at both ends of
nums. Letbest[left][right]be the most coins from the balloons strictly between positionsleftandright. Try every balloonkbetween them as the last one: it earnsbest[left][k] + best[k][right]plusvals[left] × vals[k] × vals[right]. Fill short gaps before long ones.
Solution
Each burst changes who is next to whom, so the first balloon you burst does not split the row: its two sides become neighbours. The last balloon to burst in a stretch does. It stands while everything else goes, so the stretches on its two sides are independent, and an interval table over stretches solves the problem in O(n³).
Try every bursting order
Correct, but does not finish on the largest tests
Intuition
Pick a balloon, collect left × value × right, remove it, and solve the shorter row the same way, keeping the best total over every choice. It tries every order, so it is correct.
The first burst has n choices, the next n-1, and so on: n! orders, already 479,001,600 for 12 balloons. Remembering results per set of standing balloons does not help, since there are 2^n sets.
Algorithm
- Write
burstAll(row), the most coins from the balloons inrow, 0 for an empty row. - For each position
k, earnleft × row[k] × right, using 1 past either end, plusburstAllof the row withoutrow[k]. - Return the best total over all
k, and callburstAll(nums).
def maxCoins(nums):
# Most coins you can still collect from the balloons in row
def burst_all(row):
top = 0
for k in range(len(row)):
left = row[k - 1] if k > 0 else 1
right = row[k + 1] if k + 1 < len(row) else 1
# Burst row[k] now, then do as well as possible with the rest
coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
top = max(top, coins)
return top
return burst_all(nums)Recursion on the last balloon, with a memo
Intuition
Pad the row with a 1 at each end: vals = [1] + nums + [1]. The pads never burst and stand in for the missing neighbours. Let solve(left, right) be the most coins from the balloons strictly between two standing positions.
Say k bursts last in that gap. Every other balloon in it bursts while k stands like a wall, so the part between left and k sees only its own balloons and two fixed borders, and so does the part between k and right. When k bursts, its neighbours are exactly left and right. So the best for the gap is, over every k, the best of the two parts plus vals[left] × vals[k] × vals[right]. The answer is the gap between the two pads. About n²/2 gaps each try up to n balloons, so a memo makes it O(n³).
Algorithm
- Build
valsasnumswith a 1 added at each end, and setmto its length. - Make an
m × mmemo filled with -1. - Write
solve(left, right): return 0 ifright - left < 2, and the stored value if there is one. - Otherwise try every
kstrictly between them as the last balloon, keep the largestsolve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right], and store it. - Return
solve(0, m-1).
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
memo = [[-1] * m for _ in range(m)]
# Most coins from the balloons strictly between left and right
def solve(left, right):
if right - left < 2:
return 0
if memo[left][right] >= 0:
return memo[left][right]
top = 0
for last in range(left + 1, right):
# last bursts after every other balloon in the gap
coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
top = max(top, coins)
memo[left][right] = top
return top
return solve(0, m - 1)Fill the interval table by width
Intuition
The recursion only asks about narrower gaps, so fill the same table with loops, narrow gaps before wide ones. Then best[left][k] and best[k][right] are final whenever a wider gap needs them.
For [2, 4, 3], padded to [1, 2, 4, 3, 1], best[0][4] tries each balloon last. The 3 last gives best[0][3] = 30 plus 1 × 3 × 1, for 33, the best of the three.
The work matches the memo version, but plain loops skip millions of function calls, which makes this version several times faster in a language such as Python or R.
Algorithm
- Build
valsasnumswith a 1 added at each end, and setmto its length. - Make an
m × mtablebestfilled with 0. - For each width from 2 to
m-1, and eachleftwithright = left + widthinside the array, try everykstrictly between them. - Set
best[left][right]to the largestbest[left][k] + best[k][right] + vals[left] × vals[k] × vals[right]. - Return
best[0][m-1].
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
# best[left][right]: most coins from the balloons strictly between left and right
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
edge = vals[left] * vals[right]
top = 0
for last in range(left + 1, right):
# last goes after every other balloon in the gap,
# so left and right are its neighbours when it bursts
coins = best[left][last] + best[last][right] + edge * vals[last]
if coins > top:
top = coins
best[left][right] = top
return best[0][m - 1]
Pitfalls and edge cases
- Splitting on the first burst with its original neighbours,
nums[k-1] × nums[k] × nums[k+1]plus the two sides. Those neighbours may already be gone: on[2, 4, 3]it reports 44, more than any real order earns. - Filling the table row by row with
leftgoing up. Thenbest[k][right]fork > leftis not computed yet and reads as 0. Fill by width, or walkleftdownward. - Marking an unsolved gap in the memo with 0. A gap of zero-valued balloons is really worth 0, so it is solved again on every visit. Use -1.
- In Lua and R the padded positions run from 1 to
m, so the answer isbest[1][m].
Frequently asked questions3
Why does Burst Balloons pick the last balloon instead of the first?
After the first burst its two sides become neighbours, so they still affect each other. The last balloon of a stretch stands while the others burst, so its two sides never meet and each is an independent subproblem. When it goes, its neighbours are the stretch's borders.
What is the time complexity of Burst Balloons?
O(n³) time and O(n²) memory: about n²/2 gaps, each trying up to n balloons as the last one. For 300 balloons that is about 4.5 × 10^6 steps. Trying every order is O(n · n!).
Can Burst Balloons be solved with a greedy order?
No. Bursting the smallest balloon first earns 24 on [2, 4, 3], where 33 is possible. Bursting whichever pays most now earns 42 on [2, 9, 2], where bursting a 2 first earns 18 + 18 + 9 = 45. Each burst changes the prices of the later ones.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def maxCoins(nums):
# Write code hereTest #1
Test #2
Test #3
Argument
nums = [2, 4, 3]
Expected Output
33