Burst Balloons
A row of balloons each has a number painted on it. When you burst one, you collect the number on it multiplied by the numbers on its two current neighbours, and then the gap closes so its neighbours become neighbours of each other. If a balloon has no neighbour on one side, treat the missing side as a balloon with the number 1. Burst every balloon and return the largest total you can collect . The order changes the total, and trying every order is far too slow. The way through is to ask, for each stretch of balloons, which one is the last one left in that stretch . When a balloon is last, its neighbours are the two walls of the stretch, which never move, so the two sides of it can be solved on their own.
Constraints
- 0 ≤ nums.length ≤ 300
- 0 ≤ numsi ≤ 100
- Every balloon must be burst
- Missing neighbours count as a balloon showing 1
Example
nums = [3, 1, 5, 8]167Explanation Burst the 1 (3*1*5 = 15), then the 5 (3*5*8 = 120), then the 3 (1*3*8 = 24), then the 8 (1*8*1 = 8). Total 167.
In plain terms
- Neighbours
- The balloons immediately left and right of the one being burst, as the row stands at that moment — not where they started.
- Padding with 1
- Adding an imaginary balloon with the number 1 at each end. Multiplying by 1 changes nothing, so it removes the need for special cases at the edges.
- Stretch
- A run of balloons between two fixed walls. The solution works out the best total for short stretches first and reuses those answers for longer ones.
- Last balloon
- The one burst at the very end inside a stretch. Choosing it first is what makes the problem split cleanly into two smaller ones.
The best bursting order for [3, 1, 5, 8], with 1s padded on each end
Four balloons, padded with a 1 at each end. Nothing burst yet.
What happens in this step
balloons = 1, 3, 1, 5, 8, 1 coins so far = 0 The padding 1s at the ends mean the balloons at the edges still have two neighbours, so one rule covers every burst.
Steps to visualize
- The row is the balloons with an imaginary 1 added at each end, labelled L and R.
- A dash means that balloon has already been burst and the gap has closed.
- The box marks the balloon being burst together with its two current neighbours.
- Each step shows the coins collected and the running total.
- This is the order the solution works out to be best; the code tries every possible last balloon to find it.
- The two padding balloons are never burst.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Four balloons, padded with a 1 at each end. Nothing burst yet.
What happens in this step
balloons = 1, 3, 1, 5, 8, 1 coins so far = 0 The padding 1s at the ends mean the balloons at the edges still have two neighbours, so one rule covers every burst.
Solution
function maxCoins(nums) {
const values = [1];
for (const num of nums) {
values.push(num);
}
values.push(1);
const n = values.length;
const best = [];
for (let i = 0; i < n; i += 1) {
best.push(new Array(n).fill(0));
}
for (let length = 2; length < n; length += 1) {
for (let left = 0; left + length < n; left += 1) {
const right = left + length;
for (let last = left + 1; last < right; last += 1) {
const coins = values[left] * values[last] * values[right] + best[left][last] + best[last][right];
if (coins > best[left][right]) {
best[left][right] = coins;
}
}
}
}
return best[0][n - 1];
}- Time
- O(n^3)
- Space
- O(n^2)
Test cases
| Input | Expected | Covers |
|---|---|---|
nums = [3, 1, 5, 8] | 167 | example from the description |
nums = [1, 5] | 10 | order matters even with only two balloons |
nums = [7] | 7 | smallest input, both neighbours are padding |
nums = [] | 0 | nothing to burst |
nums = [3, 0, 5] | 20 | a balloon worth nothing that still has to be burst |
nums = [2, 4, 6] | 66 | a slightly larger row where the best order is not left to right |