Burst Balloons

Problem: You are given n balloons. 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. After the burst, the i - 1 and i + 1 then becomes adjacent.

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

Example:

Input: nums = [6, 11]
Output: 77
Explanation:
First burst nums[0] then coins earned = 1 * 6 * 11 = 66
then burst nums[1] then coin earned =  1*11*1 = 11 so total coins earned are 66 + 11 = 77

Approach: We are going to use DP here. We are going to use 2D table say Table where Table[i][j] will tell the maximum coins earned for sub array nums[i...j]. Obviously Table[0][n - 1] will be our answer.

Now let's see how to fill this table:

1. FOR len = 1 to Length // for every possible length or every subarray
• For left = 0  to Length - len // left index of subarray
• right = i +  len - 1 // Right index of sub array so target sub array is (left...right)
• For last = left to right // Max coin earned by considering each element of sub array as last balloon to burst
• leftValue = nums[left - 1] // all the balloons are burst so we need to take the left of the subarray
• rightValue = nums[right + 1] // all the balloons are burst so we need to take the right of the subarray
• numOfCoinsEarnedBeforeLastBalloonBurst = Table[left][last - 1] // coins earned from left subarray of last balloon which will be (left...last-1)
• numOfCoinsEarnedAfterLastBalloonBurst = Table[last + 1][right] // coins earned from right subarray of last balloon which will be (last + 1...right)
• currentValue = leftValue * nums[last] * rightValue + numOfCoinsEarnedBeforeLastBalloonBurst + numOfCoinsEarnedAfterLastBalloonBurst 
• Table[left][right] = MAX(currentValue, Table[left][right]).

As usual we need to take care of corner cases in above steps which you can see in the implementation. That's all!

Implementation in C#:

        public int MaxCoinsByBurstingBalloons(int[] nums)

        {

            if (nums?.Length == 0)

            {

                return 0;

            }

            int[,] table = new int[nums.Length, nums.Length];

            for (int length = 1; length <= nums.Length; ++length)

            {

                for (int i = 0; i <= nums.Length - length; ++i)

                {

                    int j = i + length - 1;

                    for (int k = i; k <= j; ++k)

                    {

                        int left = i == 0 ? 1 : nums[i - 1];

                        int right = j == nums.Length - 1 ? 1 : nums[j + 1];

                        int beforeCoins = k == i ? 0 : table[i, k - 1];

                        int afterCoins = k == j ? 0 : table[k + 1, j];

                        table[i, j] = Math.Max(table[i, j], left * nums[k] * right + beforeCoins + afterCoins);

                    }

                }

            }

            return table[0, nums.Length - 1];

        }

Complexity: O(n^3)

Best Time to Buy and Sell Stock with Cooldown

Problem: Like the previous Buy and Sell stock problems, you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. 

You may complete as many transactions as you like with the following two restrictions:

1. You may not engage in multiple transactions at the same time (i.e. you must sell the stock before you buy again).
2. After you sell your stock, you cannot buy stock on next day. (i.e. cooldown of 1 day)

Example:

Input: [2,3,4,1,5]
Output: 5 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Approach: Like in previous problems, we are going to use DP approach here too. Let's have 2 1D Tables, say Buy where Buy[i] will tell the minimum money we can invest on buying stock till ith day and another table is Sell where Sell[i] will tell the maximum money we made till ith day by selling the stocks. Obviously Sell[n] will be our answer.

Here is how we can fill these tables:

1. Buy[0] = - Prices[0] and Buy[i] = MAX(Buy[i - 1], Sell[i - 2] - prices[i]). How? Here is the explanation:
• At a particular day i, either we don't do anything i.e. Buy[i - 1]. Take the previous day amount as we did not buy.
• Or we buy but to buy we need to serve the one day cooldown. That's why we will take Sell[i - 2]. Now if we buy we are spending Sell[i - 2] - prices[i] money. 
• We take the maximum of above these two numbers (hint: negative numbers) and assign it to Buy[i].
2. Sell[i] = Max(Sell[i - 1], Buy[i - 1] + prices[i]). Here is the explanation why:
• We can decide not to do any thing. In that case we will just take the previous day's amount and assign that is Sell[i - 1].
• We can decide to sell. In that case we will get Buy[i - 1] + prices[i]. Buy[i - 1] will give the minimum amount spent on buying till (i - 1)th day. 
• We take the maximum of above these two numbers and assign it to Sell[i].

We need to take care of some corner conditions and we are good to go. This will solve the problem in linear time which is very good but can we do something to optimize it further? It is obvious that we can't optimize time complexity as we have to touch each and every element of Prices array to decide the maximum profit. Then what we can do?

We can reduce space complexity. If you see we are using O(n) space which is not required. If we see closely at the above algorithm, we will find out that to calculate Buy[i] and Sell[i], we just need Buy[i - 1], Sell [i - 1] and Sell [i - 2]. That means we can use limited number of variables instead of maintaining two whole arrays to store these values. 

Let's say sell_1 is Sell[i - 1], sell_2 is Sell[i - 2] and buy_1 is Buy[i - 1]. For Buy[i] and Sell[i], we will use variables say currBuy and currSell respectively. Now our changed algorithm will look like: 

1. buy_1 = -Prices[0], sell_2 = 0, sell_1 = 0, currBuy = 0, currSell = 0
2. FOR i := 1 To n
• currBuy = MAX(buy_1, sell_2 - Prices[i])
• currSell = MAX(sell_1, buy_1 + Prices[i])
• sell_2 = sell_1
• sell_1 = currSell
• buy_1 = currBuy
3. Return currSell

You can see there is not much of change as such in algorithm except using variables instead of arrays. Hopefully its clear now and we can go to the implementation.

 

Implementation in C#:

        public int MaxProfitWithCoolDown(int[] prices)

        {

            if (prices?.Length <= 1)

            {

                return 0;

            }

            int buy_1 = -prices[0], sell_2 = 0, sell_1 = 0, currBuy, currSell = 0;

            for (int i = 1; i < prices.Length; ++i)

            {

                currBuy = Math.Max(buy_1, sell_2 - prices[i]);

                currSell = Math.Max(sell_1, buy_1 + prices[i]);

                sell_2 = sell_1;

                sell_1 = currSell;

                buy_1 = currBuy;

            }

            return currSell;

        }

Complexity: O(n)

Measuring 6L water from 4L and 9L buckets

Problem: You are given one 4 liter bucket and one 9 liter bucket. The buckets have no measurement lines on them either. How could you measure exactly 6 liter using only these buckets given you have as much extra water as you need.

Solution: Let's say 4L bucket is Bucket_4 and 9L bucket is Bucket_9. Initial value is [Bucket_4: 0, Bucket_9: 0](empty buckets). We can measure 6 liter by following below steps: 

1. Fill Bucket_9. [Bucket_4: 0, Bucket_9: 9]
2. Fill Bucket_4 from Bucket_9. [Bucket_4: 4, Bucket_9: 5]
3. Empty Bucket_4. [Bucket_4: 0, Bucket_9: 5]
4. Fill Bucket_4 from Bucket_9. [Bucket_4: 4, Bucket_9: 1]
5. Empty Bucket_4. [Bucket_4: 0, Bucket_9: 1]
6. Fill Bucket_4 (remaining 1 L water in Bucket_9) from Bucket_9. [Bucket_4: 1, Bucket_9: 0]
7. Fill Bucket_9. [Bucket_4: 1, Bucket_9: 9]
8. Fill Bucket_4 from Bucket_9. Bucket_4 can only take 3L more as 1L is already there in Bucket_4. [Bucket_4 : 4, Bucket_9: 6]

Now you can see that at step 8 Bucket_9 will have 6L (9 - 3) water.

[Google Question][LeetCode] Additive Number

Problem: Additive number is a string whose digits can form additive sequence. A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two. 

Given a string containing only digits, write a method to check if input string is an additive number. Please note that numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example:

Input: "1235813"
Output: true
Explanation: The digits can form an additive sequence: 1, 2, 3, 5, 8, 13. 
             1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13

Approach: The problem can be solved using recursion. Basically what we want to do is choose the starting two numbers which can form additive sequence so we we will choose 2 starting number say num1 and num2 as 1 by 1 of every length possible and see if selecting them as starting numbers are forming additive sequence.

In the method we will see if sum of num1 and num2 is a prefix of rest of the string. If yes, then we can call the method recursively by taking first number as num2 and second number as sum of num1 and num2 and rest of the string as third argument(excluding sum). 

If anywhere we find that current sum is not a prefix of remaining string then we return false. We continue to call the method recursively till we reach to the end that means remaining string become empty.

At any point we find a solution we return true. We can be smart about choosing the numbers as length of sum of two numbers can't be less than any of the operand's (number) length so we can loop till (length of string)/2 for first number and (length of string – first number’s length)/ 2 for second number to ignore invalid result.

Implementation in C#:

        public static bool IsAdditiveNumber(string num)

        {

            if (num?.Length < 3)

            {

                return false;

            }

            int length = num.Length;

            for (int i = 1; i <= length / 2; ++i)

            {

                for (int j = 1; j <= (length - i) / 2; ++j)

                {

                    if (IsAdditiveSequence(num.Substring(0, i), num.Substring(i, j), num.Substring(i + j)))

                    {

                        return true;

                    }

                }

            }

            return false;

        }

        private static bool IsAdditiveSequence(string str1, string str2, string remainingString)

        {

            if (!IsValid(str1) || !IsValid(str2))

            {

                return false;

            }

            if (remainingString == string.Empty)

            {

                return true;

            }

            long num1 = long.Parse(str1);

            long num2 = long.Parse(str2);

            string currSum = (num1 + num2).ToString();

            if (remainingString.Length < currSum.Length || remainingString.Substring(0, currSum.Length) != currSum)

            {

                return false;

            }

            return IsAdditiveSequence(str2, currSum, remainingString.Substring(currSum.Length));

        }

        private static bool IsValid(string str)

        {

            if(str.Length > 1 && str[0] == '0')

            {

                return false;

            }

            return true;

        }

Complexity: O(n^3)

Range Sum Query 2D

Problem: Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). Implement the NumMatrix class:

1. NumMatrix(int[][] matrix) Initializes the object with the 2D integer array matrix.
2. int SumRegion(int row1, int col1, int row2, int col2) Return the sum of the elements of the matrix  in the region where (row1, col1) is left top corner and (row2, col2) is the right bottom corner so you can safely assume row1 <= row2 and col1 <= col2.

Example:

Given matrix = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16]
]

SumRegion(1, 1, 2, 2) -> 34 (6 + 7 + 10 + 11 = 34)
SumRegion(0, 0, 2, 1) -> 33 (1 + 2 + 5 + 6 + 9 + 10 = 33)

Approach: One obvious approach is to save input matrix as is and in SumRegion method we can iterate through every element of the input region and return the sum. This will work but SumRegion will take O(m*n) time. We need to optimize it.

Another approach is we can use the approach of previous problem Range Sum Query (1D array). We can treat each row as separate array. The same precomputation and SumRange method can be applied on each and every row and then we can take the sum of all the rows(arrays) and return. It will take O(n) time which is way better than the brute force approach. Can we optimize it further? Let's see how:

We can precompute a cumulative region sum with respect to the origin at (0, 0). That means we can have a matrix say SumMatrix where SumMatrix[i][j] will have the sum of every element in the region with (0, 0) as left top corner and (i, j) as right bottom corner. In simple language:

SumMatrix[i][j] = Sum of all InputMatrix[x][y] where 0 <= x <= i and 0 <= y <= j

If we use pencil and paper and calculate cumulative sum in this way we will find out that:

SumMatrix[i][j] = SumMatrix[i][j-1] + SumMatrix[i-1][j] + InputMatrix[i][j] - SumMatrix[i-1][j-1]

Let's visualize it using an example. Take the example from the description:

Now let's see how we can calculate SumMatrix[1][1]:

If you see to calculate SumMatrix[1][1] we need sum of region (0,0) to (0, 1) that is SumMatrix[0][1] and region (0, 0) to (1, 0) that is SumMatrix[1][0] and current element. But If you see in this sum SumMatrix[0][0] came 2 times so we need to subtract it. That means:

SumMatrix[1][1] = SumMatrix[1][0] + SumMatrix[0][1] + InputMatrix[1][1] - SumMatrix[0][0]

If you see the above calculation, it matches with the statement I have given to calculate SumMatrix[i][j].

Now Let's see how we can calculate sum of the input region efficiently. Here is the calculated SumMatrix for the given example:

Say we want to calculate sum of the region (1, 1) to (2, 2):

Here is how we can calculate it:

Here is the sum of region (0, 0) to (2, 2) which is SumMatrix[2][2]:

But we don't want this. We actually want the following:

So looking at the picture we can say our target sum will be:

Sum of Region (0, 0) to (2, 2) - Sum of Region (0, 0) to (0, 2) - Sum of Region (0,0) to (2, 0) + Sum of Region (0, 0) to (0, 0) 

= SumMatrix[2][2] - SumMatrix[0][2] - SumMatrix[2][0] + SumMatrix[0][0]

We are adding Sum of region (0, 0) to (0, 0) as if you see we are subtracting it twice with (0, 0) to (0, 2) and (0, 0) to (2, 0). Now let's drive the formula by looking at it

Sum of region (r1, c1) to (r2, c2) = SumMatrix[r2][c2] - SumMatrix[r1-1][c2] - SumMatrix[r2][c1-1] + SumMatrix[r1-1][c1-1]

That's all. Hopefully you could understand the approach easily.

Implementation in C#:

    public class NumMatrix

    {

        public NumMatrix(int[][] matrix)

        {

            if (matrix.Length > 0 && matrix[0].Length > 0)

            {

                this.sumMatrix = new int[matrix.Length + 1, matrix[0].Length + 1];

                for (int i = 1; i < this.sumMatrix.GetLength(0); ++i)

                {

                    for (int j = 1; j < this.sumMatrix.GetLength(1); ++j)

                    {

                        this.sumMatrix[i, j] = this.sumMatrix[i, j - 1] + this.sumMatrix[i - 1, j] + matrix[i - 1][j - 1] - this.sumMatrix[i - 1, j - 1];

                    }

                }

            }

        }

        public int SumRegion(int row1, int col1, int row2, int col2)

        {

            if (this.sumMatrix == null)

            {

                return 0;

            }

            if (row1 == 0 && col1 == 0)

            {

                return this.sumMatrix[row2 + 1, col2 + 1];

            }

            

            return this.sumMatrix[row2 + 1, col2 + 1] - this.sumMatrix[row1, col2 + 1] - this.sumMatrix[row2 + 1, col1] + this.sumMatrix[row1, col1];

        }

        private int[,] sumMatrix;

    }

Complexity: O(m*n) for precomputation and O(1) for SumRegion.

Range Sum Query

Problem: Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Implement the NumArray class:

1. NumArray(int[] nums) Initializes the object with the integer array nums.
2. int sumRange(int i, int j) Return the sum of the elements of the nums array in the range [i, j] inclusive (i.e., sum(nums[i], nums[i + 1], ... , nums[j]))

Example:

Input
Array = [1, 2, 3, 4]
SumRange(1, 2)
SumRange(1, 3)
Output
5
9
Explanation
NumArray numArray = new NumArray([1, 2, 3, 4]);
numArray.SumRange(1, 2); // return 5 (2 + 3)
numArray.SumRange(1, 3); // return 9 (2 + 3 + 4) 

Approach: We can save the input array as it is and then whenever SumRange method is called. We can do the following:

• sum = 0
• For itr = i To j
• sum += array[itr]
• return sum

But then each SumRange call will take O(n) time. Let's see how we can make it better; Instead of saving the input array as it is what we can do is we can save the cumulative sum. That means we can have a array say "Sums" where Sums[i] will contain the cumulative sum of elements from [0...i] of input array:

Sums[i] = arr[0] + arr[1] + arr[2] + ... + arr[i]

Once we saved this array. SumRange(i, j) will be very simple to implement:

• IF i == 0 THEN return Sums[j]
• ELSE return Sums[j] - Sums[i - 1]

That's it!

Implementation in C#:

    public class NumArray

    {

        public NumArray(int[] nums)

        {

            if (nums?.Length > 0)

            {

                this.sums = new int[nums.Length];

                if (nums.Length > 0)

                    this.sums[0] = nums[0];

                for (int i = 1; i < nums.Length; ++i)

                {

                    this.sums[i] = this.sums[i - 1] + nums[i];

                }

            }

        }

        public int SumRange(int i, int j)

        {

            if (this.sums?.Length <= 0)

            {

                return 0;

            }

            return i == 0 ? this.sums[j] : this.sums[j] - this.sums[i - 1];

        }

        private int[] sums;

    }

Complexity: O(n) for constructor and O(1) for SumRange

Remove Invalid Parentheses

Problem: Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Example(Taken from leetcode):

Input: "()())()"
Output: ["()()()", "(())()"]

Approach: It looks like a backtracking problem(removing 1,2,3....n parenthesis and check if they are valid strings or not).

We can use BFS to optimize it. We can say str1 and str2 are connected if removing one parentheses from str1 forms str2. If we form a graph in this way and while traversing (BFS), at a particular level we find that a valid string is found then we add it to our result and also now we know that we don't need to move to next level as we want to remove minimum number of parenthesis to make string valid. 

Implementation in C#:

        public static IList<string> RemoveInvalidParentheses(string s)

        {

            if (string.IsNullOrWhiteSpace(s))

            {

                return new List<string>();

            }

            List<string> result = new List<string>();

            // BFS

            HashSet<string> visited = new HashSet<string>();

            Queue<string> queue = new Queue<string>();

            queue.Enqueue(s);

            visited.Add(s);

            // If we find valid string, we don't need to go to next level.

            bool goToNextLevel = true;

            while(queue.Count > 0)

            {

                s = queue.Dequeue();

                if (IsStringContainsValidParentheses(s))

                {

                    result.Add(s);

                    goToNextLevel = false;

                }

                if (!goToNextLevel)

                {

                    continue;

                }

                for (int i = 0; i < s.Length; ++i)

                {

                    if (!IsParentheses(s[i]))

                    {

                        continue;

                    }

                    string subStr = s.Substring(0, i) + s.Substring(i + 1);

                    if (!visited.Contains(subStr))

                    {

                        queue.Enqueue(subStr);

                        visited.Add(subStr);

                    }

                }

            }

            return result;

        }

        private static bool IsParentheses(char ch)

        {

            return ch == '(' || ch == ')';

        }

        private static bool IsStringContainsValidParentheses(string s)

        {

            int countParentheses = 0;

            foreach(char ch in s)

            {

                if (ch == '(')

                {

                    ++countParentheses;

                }

                else if (ch == ')')

                {

                    --countParentheses;

                }

                if (countParentheses < 0)

                {

                    return false;

                }

            }

            return countParentheses == 0;

        }

Complexity: O(N * 2 ^ N)