LeetCode 53. Maximum Subarray

Questions: https://leetcode.com/problems/maximum-subarray/

This is probably a very well-known problem with a well-known solution bearing some statistician's name. The problem asked one to find the contiguous subarray that yields the maximum sum. After a while, one should realize many of the problems that ask for a optimal subset or subarray probably involves some dynamic programming. So it is all about how one goes about formulating the problem into a dynamic programming problem.

Suppose we have found the maximum contiguous subarray that ends at all indices up to n=len(nuns). The global solution is simply the maximum among these. Afterall, the global maximum has to end at some index. No the question is: given the maximum contiguous subarray at index i, how does it help with finding the solution that ended at i+1? Since by definition, we have to include i+1 element in the contiguous subarray. We only have two choices, either we only keep the element at i+1, or we extend the previous maximum continuous subarray by append the element at i+1. We will pick the larger of the two to yield a solution to that array.

\begin{equation*} F(i+1) = \text{maximize} (nums[i+1], F(i) + nums[i+1]) \end{equation*}

When the problem is framed in this way, the solution is just rather obvious. I think most people with some practice will find Dynamic Programming solutions are not not as mysterious as they first seem to be, at least for the easier questions. This algorithm is named Kadane's algorithm, those who are interested can look it up on Wikipedia.

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)

        if n >= 1:
            a = nums[0]
            curMax = a
            for i in range(1, n):
                b = max(a + nums[i], nums[i])
                if b > curMax:
                    curMax = b
                a = b
        return curMax   

References:

• Rod Cutting Problem: https://monkeyinvestment.blogspot.com/2014/09/clrs-exercise-151-3-rod-cutting-problem.html
• Coin Change: https://monkeyinvestment.blogspot.com/2020/04/leetcode-322-coin-change.html

LeetCode 322. Coin Change

Question: https://leetcode.com/problems/coin-change/

Given a list of coins, and the amount that we want to spend, what is the minimum number of coins that you can use to make up for that amount? This is a very classic dynamic programming problem. For any dynamic programming problem, there are two approaches: top-down and bottom-up. Either approach is fine, but in general, top-down is easier to reason about.

In any dynamic programming problem, the main difficulty is in framing the question to find the sub-problems that can lead to the complete solution. Fortunately for this question, the framing is quite obvious. Let F(x) be the function that yields the minium # of coins needed to make up for the amount x. Let [c1, c2, ...cn] be the coins available. To know the minimum # of coins needed for the amount x, we just need to know the min # of coins needed for x-c1, x-c2, x-c3 and so on, and find among these the minium # of coins, and finally, we will add 1 to it to get the solution. Formally, the dynamic programming problem as stated as:

 \begin{equation*} F(x) =(\underset{i \in n} {\text{min}} F(x-c_i)) + 1 \end{equation*}

The base case is the recursion is F(coin) = 1 for all coins available since any given amount = coin value will only require 1 coin. Furthermore, F(0) = 0, since there is simply no way to get amount = 0. After all, we have no 0-value coin! The following solution implements the top-down approach using recursion and memoization by initializing the mem array to store the solutions up to amount.

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        mem = [0 for i in range(amount+1)]
        def helper(amount):
            if amount == 0:
                return 0
            if amount<0:
                return -1
            if amount in coins:
                return 1
            if mem[amount]!=0:
                return mem[amount]

            minChange = float('inf')
            for coin in coins:
                change = self.coinChange(coins, amount-coin)
                if change>0 and change < minChange:
                    minChange = change +1

            if minChange == float("inf"):
                return -1
            else:
                return minChange
        
        return helper(amount)

Now, this code wouldn't pass leetcode's tests. I am pretty sure the solution is correct. It's just that the mem implementation might need to be changed to a dictionary in order for it to pass. However, I will be focusing on the bottom-up solution because most of the time, this approach will be more efficient and require a little bit more thinking. Unlike the top-down solution, the bottom-up solution builds up the solution from the base cases. Just like the mem array before, dp will be the array that we store our solutions to different amounts. We will initialize it to be all +inf except for amount=0 where we set dp[0]=0 because we want the minimum when we do the comparison, and setting initial value to +inf will force an update to a number. Essentially, we are building up the solution to amount starting from amount=1 (due to the 0 counting convention in most programming language, we are actually building up to amount+1). The good thing about building from bottom-up is that we are guaranteed that we will have what we need to compute for amount=x because the comparisons we need are already computed previously! For each amount, we simply apply the definition for each coin and find the minimum # of coins needed among all subproblems. The only caveat is when we exit the loop, we need to check if dp[amount]>amount. If this condition is met it implies that no solution can be found. Notice that when no combination can be found. dp[amount] would not be updated and will remain to be +inf. In general, any amount that has no solution will remain to be +inf because one of their sub-solutions will not be updated at all (i.e. for some sub-solution i, coin <=i will be true for all coin) rendering no update to dp[i].

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        maxNum = amount + 1
        dp = [float("inf") for _ in range(maxNum)]
        dp[0] = 0
        for i in range(1, maxNum):
            for j, coin in enumerate(coins):
                if (coin <= i):
                    dp[i] = min(dp[i], dp[i-coin]+1)
        if dp[amount] > amount:
            return -1
        else:
            return dp[amount]

LeetCode 459. Repeated Substring Pattern

Question: https://leetcode.com/problems/repeated-substring-pattern/

This is the first string related question. Lots of the String algorithm questions look innocent, but when you dig into some of these questions, it takes some genius to come up with really smart and efficient algorithm. I remember learning KMP (knuth morris pratt) algorithm in class, and it really takes me a while to first understand what the algorithm is doing and then convince myself that it works. This problem is not as hard or as complicated as the KMP algorithm. The second solution is indeed quite smart.

My initial idea is that when you keep on rotating a valid repeated substring, you will eventually get back the same string. s[i:] + s[:i] is a pythonic way to rotate a string. It is easier to understand what rotating a string means. Let's say we have "abc", we shift the string to the left by one, we will have "bca" where "a" got pushed around to the end. Shift one more time, we have "cab".

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        n = len(s)
        ans = False
        if n == 1:
            ans = False
        else:
            for i in range(1, n):
                if s[i] == s[0]:
                    ans = (s[i:] + s[:i]) == s
                    if ans:
                        break
        return ans

Here comes the smart algorithm:

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """

        return s in s[1:] + s[:-1]

Why does it work? Consider the case for a valid repeated substring. Suppose the string has a repeating pattern "abc", and it repeated twice. The string is "abcabc" then when we form the string by concatenating the substring that cut off the first character and the substring that cut off the last character. We form the string "bc[abcabc]ab", we see the original string is in there as bolded. By cutting one character off the pattern, we were taking away one repeating pattern away from the original string. However, when we concatenate the substring that takes the first character away with the substring with last charater cutoff, we will get the back the original string embedded in this new string.