Burst Balloons

Hard
884.

Burst Balloons

Burst Balloons is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Uber interviews.

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.length
  • 1 <= n <= 300
  • 0 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 300
  • 0 <= nums[i] <= 100

Hints for Burst Balloons

  1. Hint 1

    Thinking about which balloon to burst first is hard, because the array keeps changing around it.

  2. Hint 2

    Instead, decide which balloon in a range is burst last — its neighbours are then the fixed range boundaries.

  3. 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

  1. Pad: a = [1] + nums + [1].
  2. Let dp[i][j] be the best coins from bursting everything strictly inside [i, j].
  3. Try each k in [i, j] as the last burst: dp[i][k-1] + a[i-1]·a[k]·a[j+1] + dp[k+1][j].
  4. 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] and a[j+1], not a[k-1] and a[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