Burst Balloons
Description
You are given an array of n balloons, each painted with a number. When you burst the i-th balloon, you earn coins equal to the product of three values: the number on the balloon to its left, the number on the balloon itself, and the number on the balloon to its right.
If a neighboring position is out of bounds (the balloon at the far left or the far right has no neighbor on one side), treat that missing neighbor as having a value of 1.
Once a balloon is burst, it disappears, and its former left and right neighbors become adjacent to each other. Your goal is to find the order of bursting all balloons that maximizes the total coins collected.
Formally, if you burst balloon i, you earn nums[i - 1] * nums[i] * nums[i + 1] coins, where out-of-bounds neighbors are treated as 1. Return the maximum coins you can collect by bursting all the balloons.
Examples
Example 1
Input: nums = [3, 1, 5, 8]
Output: 167
Explanation: One optimal bursting order is:
- Burst balloon at index 1 (value 1): neighbors are 3 and 5 → coins = 3 × 1 × 5 = 15. Array becomes [3, 5, 8].
- Burst balloon at index 1 (value 5): neighbors are 3 and 8 → coins = 3 × 5 × 8 = 120. Array becomes [3, 8].
- Burst balloon at index 0 (value 3): left neighbor is virtual 1, right is 8 → coins = 1 × 3 × 8 = 24. Array becomes [8].
- Burst balloon at index 0 (value 8): both neighbors are virtual 1 → coins = 1 × 8 × 1 = 8. Array becomes [].
Total: 15 + 120 + 24 + 8 = 167.
Example 2
Input: nums = [1, 5]
Output: 10
Explanation: Burst the balloon with value 1 first: neighbors are virtual 1 and 5 → coins = 1 × 1 × 5 = 5. Array becomes [5]. Then burst value 5: neighbors are virtual 1 and 1 → coins = 1 × 5 × 1 = 5. Total: 5 + 5 = 10. Trying the other order yields only 6, so 10 is optimal.
Constraints
- n == nums.length
- 1 ≤ n ≤ 300
- 0 ≤ nums[i] ≤ 100
Editorial
Brute Force
Intuition
The most natural way to think about this problem is: at each step, pick one balloon to burst, earn the corresponding coins, and then solve the remaining smaller problem.
Imagine you have four gift boxes on a shelf, and opening a box earns you points based on the labels of its neighboring boxes. You could open them in any order, and the points change depending on which boxes have already been removed. To find the best possible score, you would need to try every single ordering and keep track of the highest total.
This is exactly the brute force approach: use recursion to try bursting each balloon first, compute the coins earned, then recursively solve the remaining balloons. We take the maximum across all choices.
To simplify boundary handling, we pad the original array with virtual balloons of value 1 at both ends. This way, every real balloon always has two neighbors, and we never have to special-case the edges.
Step-by-Step Explanation
Let's trace through with nums = [3, 1, 5, 8]:
Step 1: Pad the array with 1s at both ends: balloons = [1, 3, 1, 5, 8, 1]. The real balloons are at indices 1 through 4. The values at index 0 and 5 are virtual boundaries.
Step 2: We can burst any of the 4 real balloons first. Let's explore the path where we burst index 2 (value 1) first.
- Left neighbor = balloons[1] = 3, right neighbor = balloons[3] = 5
- Coins earned = 3 × 1 × 5 = 15
- Remaining balloons: [1, 3, 5, 8, 1]
Step 3: From [1, 3, 5, 8, 1], burst index 2 (value 5).
- Left neighbor = 3, right neighbor = 8
- Coins earned = 3 × 5 × 8 = 120
- Remaining: [1, 3, 8, 1]
Step 4: From [1, 3, 8, 1], burst index 1 (value 3).
- Left neighbor = 1 (virtual), right neighbor = 8
- Coins earned = 1 × 3 × 8 = 24
- Remaining: [1, 8, 1]
Step 5: From [1, 8, 1], burst the only real balloon (value 8).
- Left neighbor = 1, right neighbor = 1
- Coins earned = 1 × 8 × 1 = 8
- Remaining: [1, 1] — only virtual balloons left.
Step 6: Total for this path = 15 + 120 + 24 + 8 = 167.
Step 7: But the brute force must try ALL orderings. For example, another path: burst 3 first (coins = 1×3×1 = 3), then 1 (coins = 1×1×5 = 5), then 5 (coins = 1×5×8 = 40), then 8 (coins = 1×8×1 = 8). Total = 56 — much worse.
Step 8: With 4 balloons, there are 4! = 24 possible orderings. The recursion tries all of them (with some repeated sub-configurations). After exhaustive search, the maximum is 167.
Algorithm
- Pad the input array with 1 at both ends: balloons = [1] + nums + [1]
- Define a recursive function dfs(balloons):
- If only the two virtual boundaries remain (length == 2), return 0
- For each real balloon at index i (from 1 to length - 2):
- Compute coins = balloons[i-1] × balloons[i] × balloons[i+1]
- Create a new array with balloon i removed
- Recursively compute dfs on the smaller array
- Track the maximum of coins + recursive result
- Return the maximum
- Call dfs(balloons) and return the result
Code
class Solution {
public:
int maxCoins(vector<int>& nums) {
vector<int> balloons = {1};
for (int x : nums) balloons.push_back(x);
balloons.push_back(1);
return dfs(balloons);
}
private:
int dfs(vector<int>& balloons) {
int n = balloons.size();
if (n == 2) return 0;
int maxCoins = 0;
for (int i = 1; i < n - 1; i++) {
int coins = balloons[i - 1] * balloons[i] * balloons[i + 1];
vector<int> remaining;
for (int j = 0; j < n; j++) {
if (j != i) remaining.push_back(balloons[j]);
}
coins += dfs(remaining);
maxCoins = max(maxCoins, coins);
}
return maxCoins;
}
};class Solution:
def maxCoins(self, nums: list[int]) -> int:
balloons = [1] + nums + [1]
def dfs(arr):
if len(arr) == 2:
return 0
max_coins = 0
for i in range(1, len(arr) - 1):
coins = arr[i - 1] * arr[i] * arr[i + 1]
coins += dfs(arr[:i] + arr[i + 1:])
max_coins = max(max_coins, coins)
return max_coins
return dfs(balloons)class Solution {
public int maxCoins(int[] nums) {
List<Integer> balloons = new ArrayList<>();
balloons.add(1);
for (int n : nums) balloons.add(n);
balloons.add(1);
return dfs(balloons);
}
private int dfs(List<Integer> balloons) {
if (balloons.size() == 2) return 0;
int maxCoins = 0;
for (int i = 1; i < balloons.size() - 1; i++) {
int coins = balloons.get(i - 1) * balloons.get(i) * balloons.get(i + 1);
List<Integer> remaining = new ArrayList<>(balloons);
remaining.remove(i);
coins += dfs(remaining);
maxCoins = Math.max(maxCoins, coins);
}
return maxCoins;
}
}Complexity Analysis
Time Complexity: O(n × 2^n)
At each level of recursion, we have up to n choices of which balloon to burst. After bursting one, we recurse on n-1 balloons. This creates a recursion tree where the total number of subproblems is exponential. With the overhead of creating new arrays at each step, the total work is O(n × 2^n). For a rough bound, this is also bounded by O(n!), since there are n! possible orderings. Either way, it grows extremely fast.
Space Complexity: O(n × 2^n)
Each recursive call creates a new array of up to n elements, and the recursion depth is n (one balloon removed per level). The total memory used across all active stack frames and their associated arrays is O(n × 2^n) in the worst case.
Why This Approach Is Not Efficient
The brute force recursion explores an exponential number of bursting orderings. With n up to 300, even O(2^n) is astronomically large — far beyond what any computer can handle in reasonable time. For n = 300, we would need more operations than there are atoms in the observable universe.
The core problem is that when we decide which balloon to burst first, the remaining subproblem depends on the entire array configuration — which balloons are still present and where they are. This means the subproblems constantly change shape, making it nearly impossible to reuse previously computed results.
The key insight that unlocks an efficient solution is a perspective shift: instead of deciding which balloon to burst first, think about which balloon to burst last within a given range. When a balloon is the last one to burst in a range, its neighbors are the fixed boundary elements of that range — they don't change. This means the problem cleanly splits into two independent subproblems (left and right of the last-burst balloon), which is exactly the structure that dynamic programming can exploit.
This reversal of thinking transforms the problem from exponential to polynomial time.
Optimal Approach - Interval Dynamic Programming
Intuition
The breakthrough idea is to flip the question: instead of asking 'which balloon do I burst first?', ask 'which balloon do I burst last in this range?'
Why does this matter? When you burst a balloon first, its neighbors change for all future decisions — the problem gets tangled. But when you say balloon k is the last one to burst in a range [l, r], something beautiful happens: at the moment you finally burst balloon k, every other balloon between l and r is already gone. The only neighbors of balloon k at that moment are the fixed boundaries — arr[l-1] on the left and arr[r+1] on the right. These boundaries never change, no matter what happened inside the range.
Even better, the problem splits into two completely independent subproblems:
- Left subproblem: What is the best score from bursting all balloons between
landk-1? - Right subproblem: What is the best score from bursting all balloons between
k+1andr?
These subproblems don't interfere with each other because balloon k (the partition point) hasn't been burst yet and acts as a boundary for both sides.
We define dp[l][r] as the maximum coins obtainable by bursting all balloons in the range [l, r]. For each range, we try every balloon k as the last to burst and take the maximum:
dp[l][r] = max over all k in [l, r] of: dp[l][k-1] + dp[k+1][r] + arr[l-1] × arr[k] × arr[r+1]
We pad the original array with 1s at both ends so boundaries are always valid. The final answer is dp[1][n], representing all original balloons.
Step-by-Step Explanation
Let's trace through with nums = [3, 1, 5, 8]:
Step 1: Pad the array: arr = [1, 3, 1, 5, 8, 1]. Create a DP table where dp[l][r] = max coins from bursting all balloons in range [l, r]. Initialize all entries to 0. We fill from small ranges to large.
Step 2: Single-balloon range dp[4][4] (balloon 8). Only choice: k=4 is last. Coins = arr[3] × arr[4] × arr[5] = 5 × 8 × 1 = 40. So dp[4][4] = 40.
Step 3: Single-balloon range dp[3][3] (balloon 5). k=3: Coins = arr[2] × arr[3] × arr[4] = 1 × 5 × 8 = 40. So dp[3][3] = 40.
Step 4: Two-balloon range dp[3][4] (balloons 5, 8). Try k=3 as last: 1×5×1 + dp[3][2] + dp[4][4] = 5 + 0 + 40 = 45. Try k=4 as last: 1×8×1 + dp[3][3] + dp[5][4] = 8 + 40 + 0 = 48. Best is 48.
Step 5: Single-balloon range dp[2][2] (balloon 1). k=2: Coins = arr[1] × arr[2] × arr[3] = 3 × 1 × 5 = 15. So dp[2][2] = 15.
Step 6: Two-balloon range dp[2][3] (balloons 1, 5). Try k=2: 3×1×8 + 0 + 40 = 64. Try k=3: 3×5×8 + 15 + 0 = 135. Best is 135.
Step 7: Three-balloon range dp[2][4] (balloons 1, 5, 8). Try k=2: 3×1×1 + 0 + 48 = 51. Try k=3: 3×5×1 + 15 + 40 = 70. Try k=4: 3×8×1 + 135 + 0 = 159. Best is 159.
Step 8: Single-balloon range dp[1][1] (balloon 3). k=1: Coins = arr[0] × arr[1] × arr[2] = 1 × 3 × 1 = 3. So dp[1][1] = 3.
Step 9: Two-balloon range dp[1][2] (balloons 3, 1). Try k=1: 1×3×5 + 0 + 15 = 30. Try k=2: 1×1×5 + 3 + 0 = 8. Best is 30.
Step 10: Three-balloon range dp[1][3] (balloons 3, 1, 5). Try k=1: 1×3×8 + 0 + 135 = 159. Try k=2: 1×1×8 + 3 + 40 = 51. Try k=3: 1×5×8 + 30 + 0 = 70. Best is 159.
Step 11: Full range dp[1][4] (all balloons 3, 1, 5, 8). Try k=1: 1×3×1 + 0 + 159 = 162. Try k=2: 1×1×1 + 3 + 48 = 52. Try k=3: 1×5×1 + 30 + 40 = 75. Try k=4: 1×8×1 + 159 + 0 = 167. Best is 167.
Step 12: Return dp[1][4] = 167.
Burst Balloons — Filling the Interval DP Table — Watch how the DP table is filled from small intervals to large, building up to the final answer dp[1][4] = 167.
Algorithm
- Pad the input array: arr = [1] + nums + [1], giving n+2 elements
- Create a 2D DP table of size (n+2) × (n+2), initialized to 0
- Iterate
lfrom n down to 1 (process smaller left indices last):- For each
l, iteraterfrom l to n (increasing range size):- For each
kfrom l to r (try each balloon as last to burst):- Compute coins = arr[l-1] × arr[k] × arr[r+1] + dp[l][k-1] + dp[k+1][r]
- Update dp[l][r] = max(dp[l][r], coins)
- For each
- For each
- Return dp[1][n] — the maximum coins from bursting all original balloons
Code
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
// Pad with virtual balloons of value 1
vector<int> arr(n + 2);
arr[0] = arr[n + 1] = 1;
for (int i = 0; i < n; i++) {
arr[i + 1] = nums[i];
}
// dp[l][r] = max coins from bursting all in range [l, r]
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
// Fill from small ranges to large
for (int l = n; l >= 1; l--) {
for (int r = l; r <= n; r++) {
for (int k = l; k <= r; k++) {
int coins = arr[l - 1] * arr[k] * arr[r + 1];
coins += dp[l][k - 1] + dp[k + 1][r];
dp[l][r] = max(dp[l][r], coins);
}
}
}
return dp[1][n];
}
};class Solution:
def maxCoins(self, nums: list[int]) -> int:
n = len(nums)
# Pad with virtual balloons of value 1
arr = [1] + nums + [1]
# dp[l][r] = max coins from bursting all in range [l, r]
dp = [[0] * (n + 2) for _ in range(n + 2)]
# Fill from small ranges to large
for l in range(n, 0, -1):
for r in range(l, n + 1):
for k in range(l, r + 1):
coins = arr[l - 1] * arr[k] * arr[r + 1]
coins += dp[l][k - 1] + dp[k + 1][r]
dp[l][r] = max(dp[l][r], coins)
return dp[1][n]class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
// Pad with virtual balloons of value 1
int[] arr = new int[n + 2];
arr[0] = arr[n + 1] = 1;
for (int i = 0; i < n; i++) {
arr[i + 1] = nums[i];
}
// dp[l][r] = max coins from bursting all in range [l, r]
int[][] dp = new int[n + 2][n + 2];
// Fill from small ranges to large
for (int l = n; l >= 1; l--) {
for (int r = l; r <= n; r++) {
for (int k = l; k <= r; k++) {
int coins = arr[l - 1] * arr[k] * arr[r + 1];
coins += dp[l][k - 1] + dp[k + 1][r];
dp[l][r] = Math.max(dp[l][r], coins);
}
}
}
return dp[1][n];
}
}Complexity Analysis
Time Complexity: O(n³)
We have three nested loops. The outer loop iterates l from n down to 1 (n iterations). For each l, the middle loop iterates r from l to n (up to n iterations). For each (l, r) pair, the inner loop iterates k from l to r (up to n iterations). Each inner iteration does O(1) work (multiplication, addition, comparison). Total: n × n × n × O(1) = O(n³). For n = 300, this is 2.7 × 10^7 operations — well within time limits.
Space Complexity: O(n²)
The padded array uses O(n) space. The 2D DP table has (n+2) × (n+2) entries, each storing a single integer, giving O(n²) space. No other data structures grow with input size. The dominant term is the DP table at O(n²).