312. Burst Balloons LeetCode Solution

In this guide, you will get 312. Burst Balloons LeetCode Solution with the best time and space complexity. The solution to Burst Balloons problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Burst Balloons solution in C++
Burst Balloons solution in Java
Burst Balloons solution in Python
Additional Resources

312. Burst Balloons LeetCode Solution image

Problem Statement of Burst Balloons

You are given n balloons, indexed from 0 to n – 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.
If you burst the ith balloon, you will get nums[i – 1] * nums[i] * nums[i + 1] coins. If i – 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:

Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100

Complexity Analysis

Time Complexity: O(n^3)
Space Complexity: O(n^2)

312. Burst Balloons LeetCode Solution in C++

class Solution {
 public:
  int maxCoins(vector<int>& nums) {
    const int n = nums.size();
    vector<vector<int>> mem(n + 2, vector<int>(n + 2));
    nums.insert(nums.begin(), 1);
    nums.insert(nums.end(), 1);
    return maxCoins(nums, 1, n, mem);
  }

 private:
  // Returns maxCoins(nums[i..j]).
  int maxCoins(const vector<int>& nums, int i, int j,
               vector<vector<int>>& mem) {
    if (i > j)
      return 0;
    if (mem[i][j] > 0)
      return mem[i][j];

    for (int k = i; k <= j; ++k)
      mem[i][j] = max(mem[i][j], maxCoins(nums, i, k - 1, mem) +
                                     maxCoins(nums, k + 1, j, mem) +
                                     nums[i - 1] * nums[k] * nums[j + 1]);

    return mem[i][j];
  }
};
/* code provided by PROGIEZ */

312. Burst Balloons LeetCode Solution in Java

class Solution {
  public int maxCoins(int[] nums) {
    final int n = nums.length;
    int[][] mem = new int[n + 2][n + 2];
    int[] extendedNums = new int[n + 2];
    System.arraycopy(nums, 0, extendedNums, 1, n);
    extendedNums[0] = 1;
    extendedNums[n + 1] = 1;
    return maxCoins(extendedNums, 1, n, mem);
  }

  // Returns maxCoins(nums[i..j]).
  private int maxCoins(int[] nums, int i, int j, int[][] mem) {
    if (i > j)
      return 0;
    if (mem[i][j] > 0)
      return mem[i][j];

    for (int k = i; k <= j; ++k)
      mem[i][j] = Math.max(mem[i][j],                          //
                           maxCoins(nums, i, k - 1, mem) +     //
                               maxCoins(nums, k + 1, j, mem) + //
                               nums[i - 1] * nums[k] * nums[j + 1]);

    return mem[i][j];
  }
}
// code provided by PROGIEZ

312. Burst Balloons LeetCode Solution in Python

class Solution:
  def maxCoins(self, nums: list[int]) -> int:
    n = len(nums)
    nums = [1] + nums + [1]

    @functools.lru_cache(None)
    def dp(i: int, j: int) -> int:
      """Returns maxCoins(nums[i..j])."""
      if i > j:
        return 0
      return max(dp(i, k - 1) +
                 dp(k + 1, j) +
                 nums[i - 1] * nums[k] * nums[j + 1]
                 for k in range(i, j + 1))

    return dp(1, n)
 # code by PROGIEZ