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

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.