Burst Balloons — Solution in Python, Java & C++
Burst Balloons solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
Burst Balloons is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Uber interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Balloon i is painted with the number nums[i]. Bursting balloon i earns nums[i-1] · nums[i] · nums[i+1] coins, where an out-of-range neighbour counts as 1. After a burst, its neighbours become adjacent.
Burst all the balloons and return the maximum coins you can collect.
Example 1
Input: nums = [3,1,5,8]
Output: 167
Explanation: Burst 1, then 5, then 3, then 8.
Example 2
Input: nums = [1,5]
Output: 10
Example 3
Input: nums = [7]
Output: 7
Constraints
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
Hints for Burst Balloons
Hint 1
Thinking about which balloon to burst first is hard, because the array keeps changing around it.
Hint 2
Instead, decide which balloon in a range is burst last — its neighbours are then the fixed range boundaries.
Hint 3
Pad the array with 1 at both ends so every range has well-defined boundaries.
How to solve Burst Balloons
Interval DP on 'last to burst'. If balloon k is the last one popped inside [i, j], then at that moment its neighbours are exactly a[i-1] and a[j+1], which are outside the range and therefore fixed — that is what makes the subproblems independent.
Approach
- Pad:
a = [1] + nums + [1]. - Let
dp[i][j]be the best coins from bursting everything strictly inside[i, j]. - Try each
kin[i, j]as the last burst:dp[i][k-1] + a[i-1]·a[k]·a[j+1] + dp[k+1][j]. - Fill by increasing interval length; the answer is
dp[1][n].
Why it works
Choosing the first burst leaves two sides that are no longer independent — the surviving balloons can interact across the gap. Choosing the last burst inside a range fixes that balloon's neighbours to the range's outside boundaries, so the left and right sub-ranges never influence each other and their optima simply add.
Complexity
- Time —
O(n³) - Space —
O(n²)
Pitfalls
- Recursing on 'first to burst' gives overlapping, non-independent subproblems and a wrong answer.
- The multiplication uses the range boundaries
a[i-1]anda[j+1], nota[k-1]anda[k+1]. - The padding is what makes the edge cases uniform; without it the boundaries need special handling.
Reference solution
Python
from typing import List
def maxCoins(nums: List[int]) -> int:
n = len(nums)
a = [1] + nums + [1]
dp = [[0] * (n + 2) for _ in range(n + 2)]
for length in range(1, n + 1):
for i in range(1, n - length + 2):
j = i + length - 1
for k in range(i, j + 1):
dp[i][j] = max(dp[i][j], dp[i][k - 1] + a[i - 1] * a[k] * a[j + 1] + dp[k + 1][j])
return dp[1][n]Java
public static int maxCoins(int[] nums) {
int n = nums.length;
int[] a = new int[n + 2];
a[0] = 1;
a[n + 1] = 1;
for (int i = 0; i < n; i++) a[i + 1] = nums[i];
int[][] dp = new int[n + 2][n + 2];
for (int len = 1; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k <= j; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + a[i - 1] * a[k] * a[j + 1] + dp[k + 1][j]);
}
}
}
return dp[1][n];
}C++
int maxCoins(vector<int>& nums) {
int n = (int) nums.size();
vector<int> a(n + 2, 1);
for (int i = 0; i < n; i++) a[i + 1] = nums[i];
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
for (int len = 1; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i][k - 1] + a[i - 1] * a[k] * a[j + 1] + dp[k + 1][j]);
}
}
}
return dp[1][n];
}JavaScript
var maxCoins = function(nums) {
var n = nums.length;
var a = [1].concat(nums).concat([1]);
var dp = [];
for (var p = 0; p < n + 2; p++) {
var row = [];
for (var q = 0; q < n + 2; q++) row.push(0);
dp.push(row);
}
for (var len = 1; len <= n; len++) {
for (var i = 1; i + len - 1 <= n; i++) {
var j = i + len - 1;
for (var k = i; k <= j; k++) {
var val = dp[i][k - 1] + a[i - 1] * a[k] * a[j + 1] + dp[k + 1][j];
if (val > dp[i][j]) dp[i][j] = val;
}
}
}
return dp[1][n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming