LeetCode: Burst Balloons C#

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;

{
/// <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;
}
}
}


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
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.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));

• Thorough review, have some rep from me :) – dfhwze Oct 11 '19 at 19:46
• @dfhwze I didn't understand why you put a bounty on my question, but thanks you and thank you guys for the reviews – Gilad Oct 12 '19 at 6:47

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.