A. Merge Similar Items (opens new window)

Count and sort by frequency.

DETAILS

def mergeSimilarItems(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        vals = [0] * 1001
        for v, w in A: vals[v] += w
        for v, w in B: vals[v] += w
        return [[i, a] for i, a in enumerate(vals) if a]

B. Count Number of Bad Pairs (opens new window)

In a good pair, A[i] - A[j] = i - j holds, A[i] - i = A[j] - j = k where k is an arbitrary number. Thus we just collect A[i] - i for all indexes i. All the pairs except the pairs having the same A[i] - i are so called bad pairs.

DETAILS

def countBadPairs(self, A: List[int]) -> int:
        C, n, ans = collections.Counter([a - i for i, a in enumerate(A)]), len(A), 0
        return sum(a * (n - a) for a in C.values()) // 2

C. Task Scheduler II (opens new window)

Greedy.

DETAILS

def taskSchedulerII(self, A: List[int], k: int) -> int:
        prev = collections.defaultdict(int)
        cur = 0
        for a in A:
            if a not in prev or cur - prev[a] > k: 
                cur += 1
            else:
                cur += k - (cur - prev[a]) + 1
            prev[a] = cur
        
        return cur

D. Minimum Replacements to Sort the Array (opens new window)

Greedy, if A[i] > A[i + 1], we need to divide A[i] into the fewest equal parts that are no larger than A[i + 1].

DETAILS

def minimumReplacement(self, A: List[int]) -> int:
        ans, n = 0, len(A)
        for i in range(n - 2, -1, -1):
            if A[i] <= A[i + 1]:
                continue
            k = A[i] // A[i + 1] + 1 if A[i] % A[i + 1] else A[i] // A[i + 1]
            ans += k - 1
            A[i] = A[i] // k
        return ans