Category: Preparation For Quantitative Trader/Researcher Job

Question 673. Number of Longest Increasing Subsequence

Link

https://leetcode.com/problems/number-of-longest-increasing-subsequence/

My code:

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        if len(nums) ==0: return 0
        if len(nums) ==1: return 1
        #The list contains the maximum length end up with ith element in the nums
        ResultList = [[1,1]]
        #The dictionary provides the number of list given in the list
        for i in range(1,len(nums)):
            IndexList = []
            Length =1
            Num = 0
            for j in range(i):
                if nums[i]>nums[j]:
                    Length = max(Length,ResultList[j][0]+1)
                    IndexList.append(j)
            if Length != 1:
                for k in IndexList:
                    if ResultList[k][0] == Length -1:
                        Num += ResultList[k][1]
            if Num == 0:
                Num = 1
            ResultList.append([Length,Num])
        LengthList = [ResultList[i][0] for i in range(len(ResultList))]
        MaxLength = max(LengthList)
        Sum  = 0
        for s in range(len(ResultList)):
            if ResultList[s][0] == MaxLength:
                Sum += ResultList[s][1]
        return Sum

Explanation: There are two main problems in this question:1. How to determine the maximum length 2. How to count all the subsequence with maximum length. Here is the way I solve it. I construct a list L such that L[i] is a list that contains two elements. First element is the maximum length that ends up with element nums[i] and second element is the number of such subsequences. The recursion relation is as follows: for i+1 th element, we first check if it is larger than the chosen previous element. If so, then we know that the length of new List would be the maximum length of subsequence that ends up with chosen previous element plus one. Iterate through the beginning we may get the maximum length that ends up with i+1 th element. Second is to determine the number of the elements that ends up with i+1 th element and equals to the maximum length. So I do the iteration again to find total number. Notice that I initialise the length as 1 and Num as 0 because there is a situation that the i+1 th element might be smaller than all previous elements. In this situation , the maximum length would be one as itself. and the number would be 1 as just itself. Hence we iterate throught the nums list. Then we first find out the maximum length. Then we sum all the numbers that gives the maximum length. Then we return the result.

 

Question 368. Largest Divisible Subset

Link:

https://leetcode.com/problems/largest-divisible-subset/

My Code:

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        SortedNums = sorted(nums)
        if len(nums) == 0:
            return []
        if len(SortedNums ) ==1:
            return SortedNums
        else:
            #Here we design a list dp, dp[j] is the maximum length list end up with nums[j]
            StoreList = [[SortedNums[0]]]
            for i in range(1,len(SortedNums)):
                NewList =[SortedNums[i]]
                length = 1
                for j in range(i):
                    if SortedNums[i]%SortedNums[j] == 0:
                        Temp =  copy.deepcopy(StoreList[j])
                        Temp.append(SortedNums[i])
                        NewList2 = Temp
                        if len(NewList2) > length:
                            NewList = NewList2
                            length  = len(NewList)
                StoreList.append(NewList)
            Length2 = len(StoreList[0])
            ResultList = StoreList[0]
            for k in range(1,len(StoreList)):
                if len(StoreList[k])> Length2:
                    ResultList = StoreList[k]
                    Length2 = len(ResultList)
            return ResultList

Explanation: First, we need to solve the issue how to check the divisibility. The idea is that for any integers a, b , c if a|b, b|c  then a|c. Hence we just need to sort the num list. Then we design a dp list. df[j] is the maximum list end up with j the element in the number list. Then for j+1, we just need to check for any i <j+1, if nums[j+1] is divisible by nums[i] or not. If it is divisible , then we append the number into the maximum list end up with ith element. Then we pick the maximum length of all and take that as the jth element in the list.

Question 357 Count Numbers with Unique Digits

Link:

https://leetcode.com/problems/count-numbers-with-unique-digits/

My Code:

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        import math as m
        ResultList = [1,10]
        for j in range(2,n+1):
            if j<=10:
                Result = ResultList[j-1]+int(9*m.factorial(9)/(m.factorial(10-j)))
                ResultList.append(Result)
            else:
                return ResultList[10]
        return ResultList[n]

Explanation: The idea is clear. First, there are only 10 different digits, so for any n that is larger than 10, we shall consider it exactly as the situation with n = 10. Next, for each n <=10, we construct a dp, dp[n] is the total number of numbers with unique digits with maximum n digits. Then for n+1, we just need to calculate the number of numbers with unique digits  at length equals to n+1, then sum it with dp[n] to get the total number of numbers with unique digits  at length at most n+1. Then return it.

 

Question 576 Out of Boundary Paths

Link:

https://leetcode.com/problems/out-of-boundary-paths/

My Code:

class Solution:
    def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:
        Total = 0
        NumberMat = []
        for k in range(m):
            NumberMat.append([0]*n)
        NumberMat[i][j] = 1
        if m !=1 and n!=1:
            for k in range(N):
                for row in range(m):
                    if row == 0:
                        Total += sum(NumberMat[row])+NumberMat[row][0] + NumberMat[row][-1]
                    elif row == (m-1):
                        Total += sum(NumberMat[row])+NumberMat[row][0] + NumberMat[row][-1]
                    else:
                        Total =Total + NumberMat[row][0] + NumberMat[row][-1]
                NewMat = []
                for row in range(m):
                    NewList = []
                    for col in range(n):
                        if row == 0:
                            if col == 0:
                                NewValue = NumberMat[row+1][col]+NumberMat[row][col+1]
                                NewList.append(NewValue)
                            elif col == (n-1):
                                NewValue =  NumberMat[row+1][col]+NumberMat[row][col-1]
                                NewList.append(NewValue)
                            else:
                                NewValue =  NumberMat[row+1][col]+NumberMat[row][col-1]+NumberMat[row][col+1]
                                NewList.append(NewValue)
                        elif row == (m-1):
                            if col == 0:
                                NewValue = NumberMat[row-1][col]+NumberMat[row][col+1]
                                NewList.append(NewValue)
                            elif col == (n-1):
                                NewValue =  NumberMat[row-1][col]+NumberMat[row][col-1]
                                NewList.append(NewValue)
                            else:
                                NewValue =  NumberMat[row-1][col]+NumberMat[row][col-1]+NumberMat[row][col+1]
                                NewList.append(NewValue)
                        else:
                            if col == 0:
                                NewValue = NumberMat[row+1][col]+NumberMat[row][col+1]+NumberMat[row-1][col]
                                NewList.append(NewValue)
                            elif col == (n-1):
                                NewValue =  NumberMat[row+1][col]+NumberMat[row][col-1]+NumberMat[row-1][col]
                                NewList.append(NewValue)
                            else:
                                NewValue =  NumberMat[row+1][col]+NumberMat[row][col-1]+NumberMat[row][col+1]+NumberMat[row-1][col]
                                NewList.append(NewValue)

                    NewMat.append(NewList)
                NumberMat = NewMat


            return Total%(10**9+7)
        elif m ==1 and n!=1:
            for k in range(N):
                Total += 2*sum(NumberMat[0])+NumberMat[0][0] + NumberMat[0][-1]
                NewMat = []
                NewList = []
                for col in range(n):
                    if col == 0:
                        NewValue = NumberMat[0][col+1]
                        NewList.append(NewValue)
                    elif col == (n-1):

Explanation:

The DP array is defined as the number of paths that can  reach ith row , jth col in the kth step. Then we just need to iterate with the number k until n-1. For each  entry of the matrix, there are three situations: in the corner, on the side and others. For either case, we take the sum of all cells next to it as the value at that cell. For each time, we sum the possible out path( all value of cells on the boarder). Then we return the result of the total value.

Question 1423. Maximum Points You Can Obtain from Cards

Link

https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/

My Code:

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        if k>= len(cardPoints):
            return sum(cardPoints)
        else:
            RestLength = len(cardPoints) - k
            TotalSum = sum(cardPoints)
            PartSum = sum(cardPoints[0:RestLength])
            Min =PartSum
            for new in range(RestLength,len(cardPoints)):
                old = new -RestLength
                PartSum= PartSum - cardPoints[old]+cardPoints[new]
                Min = min(Min,PartSum)
            return TotalSum - Min

Explanation: The idea is clear , no matter which side you choose, the list left must be continuous and the length is total length – k. Then we just need to write an iteration to calculate minimum of the list. Notice that if we use sum function here, it will exceed time limit as sum function also originates from the iteration.

Question 1048. Longest String Chain

Link:

https://leetcode.com/problems/longest-string-chain/

My Code:

class Solution:
    def longestStrChain(self, words: List[str]) -> int:

        def PredCheck(OldString, NewString):
            if len(OldString) != (len(NewString)-1):
                return False
            else:
                for j in range(len(NewString)):
                    CheckStr = NewString[0:j]+NewString[j+1:len(NewString)]
                    if CheckStr == OldString:
                        return True
                return False
        
        #We need to sort the string list based on the length of the strings in the list
        #for i in range(1,len(words)):
           # NewList = []
          #  for j in range(len(words)):
         #       NewString = words[j]
        #        Max = 0
       #         for k in range(len(words)):
      #              OldString = words[k]
     #               if PredCheck(OldString,NewString):
    #                    Max = max(ResultList[i-1][k], Max)
   #             Value = Max+1
  #              NewList.append(Value)
 #           ResultList.append(NewList)
#        return max(ResultList[-1])
        
        NewWords = sorted(words,key = len)
        ResultList = [1]
        for i in range(1,len(NewWords)):
            NewString = NewWords[i]
            Max = 0
            for j in range(i):
                OldString = NewWords[j]
                if PredCheck(OldString,NewString):
                    Max = max(ResultList[j],Max)
            Value = Max+1
            ResultList.append(Value)
        return max(ResultList)

Explanation:

The idea of the code is following this: The matrix Mat[i][j] means the maximum string chain we may get if we can only choose i elements at most and ending element must be words[j]. The commented code is the original code. It has a time complexity of n^3. However, we may improve it, as we may notice that the order of the element in the list should not change the result. Hence we may first sort the string list by the length of the element. Then we may use one dimensional list to store the result .Here ResultList[i] means the maximum number of the string if the ending element is NewWords[i] (Sorted string list). We do not to apply n^2 check scheme as based on the sorted string list, all the possible predecessor given string NewWord[i] are included in the NewWords[k], 0<=k<i-1. Hence we just need to check with n^2 time complexity. The sort scheme (usually) has a complexity of n^2, hence the total time complexity of the code is n^2

Question 120. Triangle

Link:

https://leetcode.com/problems/triangle/

My Code:

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        TriangleLength = len(triangle)
        MinTri = [triangle[0]]
        for i in range(1,TriangleLength):
            CheckLen = len(triangle[i])
            MinList = []
            for j in range(CheckLen):
                if j == 0:
                    MinList.append(triangle[i][0]+MinTri[i-1][0])
                elif j == (CheckLen -1):
                    MinList.append(triangle[i][CheckLen-1]+MinTri[i-1][CheckLen-2])
                else:
                    Min = min(MinTri[i-1][j],MinTri[i-1][j-1])+ triangle[i][j]
                    MinList.append(Min)
            MinTri.append(MinList)
        return min(MinTri[TriangleLength-1])

Explanation: The idea is clear, for each element in the triangle, we search for the minimum path number among all the available previous element, then take the minimum to get the minimum path sum at this point.

Question 322 Coin Change

Link:

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

My Code:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        else:
            ResultList = [0]
            MinCoin = min(coins)
            for i in range(1,(amount+1)):
                if i < MinCoin:
                    ResultList.append(0)
                else:
                    AvailableCoinList = []
                    for j in range(len(coins)):
                        if coins[j]<=i:
                            AvailableCoinList.append(coins[j])
                    Min = 2**31
                    if i in AvailableCoinList:
                        ResultList.append(1)
                    else:
                        for k in AvailableCoinList:
                            if ResultList[i-k] != 0:
                                Min = min(ResultList[i-k],Min)
                        if Min == 2**31:
                            ResultList.append(0)
                        else:
                            ResultList.append(Min+1)
            if ResultList[amount] == 0:
                return -1
            else:
                return ResultList[amount]

Explanation: The code follows this idea: For an amount n, we check all the coins that is smaller than it, for example k_1,…,k_j as j coins that is available. The DP[i] list is the minimum amount of coins that can achieve amount i with given coin List. so We check all the available coin i in the list, then we take the minimum of all n-i. There are several situations: first, if n is in the coin list, then the answer is 1. Next if n is not in the coin list, then if all the previous n-k_j  are zero, then it means we cannot get the number here, hence we return 0. Otherwise we take the minimum of all non- zero n- k_j and then take the minimum and plus 1.

Question 300. Longest Increasing Subsequence

Link

https://leetcode.com/problems/longest-increasing-subsequence/

My Code:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) ==0:
            return 0
        else:
            ResultList = [1]
            for i in range(1,len(nums)):
                Max = 1
                for j in range(i):
                    if nums[i]>nums[j]:
                        Max = max(Max,ResultList[j]+1)
                ResultList.append(Max)
            return max(ResultList)

Explanation: we set the ResultList as the longest subsequence up to element k in the sequence. Then for next element, we just need to check if it is larger than the previous elements. If it is larger, then we just append the element to the previous subsequence, corresponding to the code ResultList[j] +1, then we take the Max among all the possible choices. if it is smaller then all previous elements, then we set the number as 1 in the list.

Then we just need to return the maximum among all the result in the list.

Question 494. Target Sum

Link:

 

My Code:

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        LargestSum = sum(nums)
        SmallestSum = -LargestSum
        if LargestSum<S or SmallestSum>S:
            return 0
        else:
            ResultMat = []
            for l in range(len(nums)):
                List = [0]*(LargestSum*2+1)
                ResultMat.append(List)
            ResultMat[0][nums[0]] = ResultMat[0][nums[0]]+1
            ResultMat[0][-nums[0]] = ResultMat[0][-nums[0]]+1
            for i in range(1,len(nums)):
                for j in range(-LargestSum,LargestSum+1,1):
                    Index1 = j-nums[i]
                    Index2 = j+nums[i]
                    if Index1 <-LargestSum:
                        Value1 =0
                    else:
                        Value1 = ResultMat[i-1][Index1]
                    if Index2> LargestSum:
                        Value2 = 0
                    else:
                        Value2 = ResultMat[i-1][Index2]
                    Value = Value1+Value2
                    ResultMat[i][j] = Value
            return ResultMat[len(nums)-1][S]

Explanation: I use a two dimension matrix to store the data. The row is the ith element of the original list, the column is the Sum j and the value stored in the matrix[i][j] is the total number that can achieve value j at the ith index. Then to for i+1 Index, the only way to achieve the sum j is that we have achieved j+ nums[i+1] or j-nums[i+1] at the index i. Hence we just sum these two values together to get the total number that can achieve j at i+1.