A. Find the Difference of Two Arrays (opens new window)

Hashtable.

DETAILS

def findDifference(self, A: List[int], B: List[int]) -> List[List[int]]:
        sa, sb = set(A), set(B)
        return [list(set([a for a in A if a not in sb])), list(set([b for b in B if b not in sa]))]

B. Minimum Deletions to Make Array Beautiful (opens new window)

Greedy.

DETAILS

def minDeletion(self, A: List[int]) -> int:
        ans = 0
        for i in range(len(A) - 1):
            if A[i] == A[i + 1] and (i - ans) % 2 == 0:
                ans += 1
        return ans + (len(A) - ans) % 2

C. Find Palindrome With Fixed Length (opens new window)

Notice all the palidromes are of the same length. Thus we don't need any backtracking methods to find the palidrome, but just build the first half from increasing natural number.

For example: Given length = 4:

• The first palidrome 1001 is made by 10.
• The second palidrome 1111 is made by 11.
• The third palidrome 1221 is made by 12.

DETAILS

def kthPalindrome(self, A: List[int], m: int) -> List[int]:
        k = math.ceil(m/2)
        base, most = 10 ** (k - 1), 9 * 10 ** (k - 1)
        ans = []  
        
        for a in A:
            if a > most:
                ans.append(-1)
            else:
                cur = str(base + a - 1)
                if m % 2:
                    cur += cur[:-1][::-1]
                else:
                    cur += cur[::-1]
                ans.append(int(cur))
        return ans

D. Maximum Value of K Coins From Piles (opens new window)

DP.

DETAILS

def maxValueOfCoins(self, A: List[List[int]], k: int) -> int:
        n = len(A)
        presum, dp = [[0] + list(itertools.accumulate(a)) for a in A], [[0] * (k + 1) for _ in range(n)]
        
        cur = 0
        for i in range(min(k + 1, len(presum[0]))):
            dp[0][i] = presum[0][i]
        if k + 1 > len(presum[0]):
            for i in range(len(presum[0]), k + 1):
                dp[0][i] = dp[0][i - 1]
        
        for p in range(1, n):
            for c in range(1, k + 1):
                dp[p][c] = max(dp[p - 1][c - i] + presum[p][i] for i in range(min(len(A[p]), c) + 1))
                
        return dp[-1][-1]