LeetCode: Burst Balloons C#

Question

https://leetcode.com/problems/burst-balloons/

Given n balloons, indexed from 0 to n-1, each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If you burst balloon i, the number of coins you will get is calculated as: $$ nums[left] * nums[i] * nums[right] $$Here, left and right are adjacent indices of i. After the burst, left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

You may imagine $$ nums[-1] = nums[n] = 1 $$They are not real therefore you can not burst them. 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:
Input: [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

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace RecurssionQuestions
{
 /// <summary>
 /// https://leetcode.com/problems/burst-balloons/
 /// </summary>
 [TestClass]
 public class BurstBalloonsTest
 {
 [TestMethod]
 public void TestExample()
 {
 int[] nums = {3, 1, 5, 8};
 BurstBalloonsClass burst = new BurstBalloonsClass();
 Assert.AreEqual(167, burst.MaxCoins(nums));
 }
 }
 public class BurstBalloonsClass
 {
 public int MaxCoins(int[] nums)
 {
 int[] numbers = new int[nums.Length +2]; // we add 2 because of the question
 // nums[-1] = nums[n] = 1
 int n = 1;
 foreach (var x in nums)
 {
 if (x > 0) // we care only about positive values for profit
 {
 numbers[n++] = x;
 }
 }
 numbers[0] = numbers[n++] = 1;
 int[][] memo = new int[n][];
 for (var index = 0; index < memo.Length; index++)
 {
 memo[index]= new int[n];
 }
 // we allocate NxN matrix for memoization
 return Burst(memo, numbers, 0, n - 1);
 }
 private int Burst(int[][] memo, int[] numbers, int left, int right)
 {
 if (left + 1 == right)
 {
 return 0;
 }
 if (memo[left][right] > 0)
 {
 return memo[left][right];
 }
 int ans = 0;
 // we try all the options between left and right
 // we compare the answers of all of the options and the maxmial one
 // if poped all of the ballons from left to u and from i to right we have only an option to pop
 // numbers[left] * numbers[i] * numbers[right]
 for (int i = left + 1; i < right; ++i)
 {
 ans = Math.Max(ans, numbers[left] * numbers[i] * numbers[right]
 + Burst(memo, numbers, left, i)
 + Burst(memo, numbers, i, right));
 }
 memo[left][right] = ans;
 return ans;
 }
 }
}

Answer 1

Some things come to mind when I read your code.

There is a nice feature on arrays in C# called CopyTo(). It gives you the possibility to copy an array without using a loop. Like so:

int[] newNums = new int[n];
nums.CopyTo(newNums, 1); 
newNums[0] = newNums[n-1] = 1; //This line I really like. 

There is also something called a multidimensional Array which basically does the same thing as int[][]. This gives you the possibility to do this:

int[,] memo = new int[n,n];

Use them together and you can remove all your loops from int maxcoins.

Regarding your actual work method Burst I would say that you make things rather confusing. When debugging, the first thing that happens is that you cache a number series which is not allowed until 3 balloons are popped. It adds [0][1][5] to the cache. A more reasonable approach would have been [0][1][2] then [0][1][3] up to [0][1][5]. After that switch to [0][2][3] etc. When you reach [0][4][5] you start over at [1][2][3].

To do that you would have to create nested loops in your Burst method:

 for (int i = left+1; i < right; ++i)
 {
 for(int j = i+1; j<= right; ++j)
 ans = Math.Max(ans, numbers[left] * numbers[i] * numbers[j]
 + Burst(memo, numbers, left, i)
 + Burst(memo, numbers, i, j));
 }

However, there is an even more simple approach to this problem and that is to actually pop the balloons in the array. This can be done easiest with a list instead of an array. But both are possible. So what you would do is to create a new set of balloons after each pop. So here caching is out of the question because you never really know what range you processed before. And to be honest I guess it would most likely slow down the process and make the code harder to read. I use the same variable names as you but in reality I would name nums and numbers as balloons and newNumbers would be named remainingBalloons. I did however change the variable i to baloonToPop to make it easier to understand what it represents. I left the adding of the ones in the code because it simplifies the Burst method.

 public void MaxCoins(List<int> nums)
 {
 nums.Insert(0, 1); //Add the ones to the array
 nums.Add(1);
 int result = Burst(nums);
 }
 private int Burst(List<int> numbers)
 {
 int result = 0;
 for (int baloonToPop = 1; baloonToPop < numbers.Count-1; baloonToPop++)
 {
 List<int> newNumbers = new List<int>();
 newNumbers.AddRange(numbers);
 newNumbers.RemoveAt(baloonToPop);
 int sumFromBaloonPop = numbers[baloonToPop - 1] * numbers[baloonToPop] * numbers[baloonToPop + 1];
 result = Math.Max(result, Burst(newNumbers) + sumFromBaloonPop);
 }
 return result;
 }

To do it with an array (in case there is a library restriction) you would have to create a new Array and then copy Subranges from the initial one instead of creating a copy of the List using AddRange + RemoveAt as above:

int[] newNumbers = new int[numbers.Length-1];
Array.ConstrainedCopy(numbers, 0, newNumbers, 0, baloonToPop);
Array.ConstrainedCopy(numbers, baloonToPop + 1, newNumbers, baloonToPop, numbers.Length - (baloonToPop + 1));

• dfhwze: Thorough review, have some rep from me :)
• Gilad: @dfhwze I didn't understand why you put a bounty on my question, but thanks you and thank you guys for the reviews

Answer 2

The comment here

int[] numbers = new int[nums.Length +2]; // we add 2 because of the question

is not really useful, it requires to read the entire question to figure out why 2 is added to the number of balloons. I would suggest something like

// Allocate array for all balloons, plus the two "imaginary" balloons 
// at positions -1 and n.

which closely matches the note from the problem description:

You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.