A. Apply Operations to an Array (opens new window)

Iterate over A, apply all the operations, then split A into two groups without ruining their original orders.

DETAILS

def applyOperations(self, A: List[int]) -> List[int]:
        for i in range(len(A) - 1):
            if A[i] == A[i + 1]:
                A[i] *= 2
                A[i + 1] = 0
        return [x for x in A if x] + [x for x in A if not x]

B. Maximum Sum of Distinct Subarrays With Length K (opens new window)

Record the last occurrence of each distinct integer. Suppose the last occurrence of integer d is pos[d], then if we find the next d during the iteration, we have to check if the distance between two d's is no less than k.

DETAILS

def maximumSubarraySum(self, A: List[int], k: int) -> int:
        pos, end, curr, ans = {}, k - 1, 0, 0
        for i, a in enumerate(A):
            curr += a
            if i >= k:
                curr -= A[i - k]
            if i - pos.get(a, -k) < k:
                end = max(end, pos[a] + k)
            pos[a] = i
            if i >= end:
                ans = max(ans, curr)
        
        return ans

C. Total Cost to Hire K Workers (opens new window)

Priority Queue, take the valid worker either by front or by tail with the least cost.

DETAILS

def totalCost(self, C: List[int], k: int, cand: int) -> int:
        H = C[:cand]
        T = C[max(cand, len(C) - cand):]
        heapify(H)
        heapify(T)
        ans, i, j = 0, cand, len(C) - 1 - cand 

        for _ in range(k): 
            if not T or H and H[0] <= T[0]: 
                ans += heappop(H)
                if i <= j: 
                    heappush(H, C[i])
                    i += 1
            else: 
                ans += heappop(T)
                if i <= j: 
                    heappush(T, C[j])
                    j -= 1
        return ans 

D. Minimum Total Distance Traveled (opens new window)

Please refer to This LC Discussion (opens new window) for my solution in English.

DP + greedy.

DETAILS

class Solution:
    def minimumTotalDistance(self, R: List[int], F: List[List[int]]) -> int:
        memo = {}
        
        R.sort()
        F.sort()
        rr, ff = len(R), len(F)
        
        def dp(r, f, res):
            if (r, f, res) in memo: 
                return memo[(r, f, res)]
            
			# Edge cases: r = rr, we have finished assigning all robots, return 0;
			# res = 0, the current factory has 0 remaning seats, move to the next factory.
            if r == rr:
                return 0
            if res == 0:
                return dp(r, f + 1, F[f + 1][1]) if f + 1 < ff else math.inf
            
			# Assign the current robot r to the current factory f.
            cur = dp(r + 1, f, res - 1) + abs(R[r] - F[f][0])
			
			# Or assign it to the next factor f + 1, if possible.
            if f + 1 < ff:
                cur = min(cur, dp(r, f + 1, F[f + 1][1]))
                
            memo[(r, f, res)] = cur
            return cur
        
        return dp(0, 0, F[0][1])