LeetCode 1122. Relative Sort Arr

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that don't appear in arr2 should be placed at the end of arr1 in ascending order.

Example 1:
Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

Constraints:
arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
Each arr2[i] is distinct.
Each arr2[i] is in arr1.

Solution:

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        arr3 = [i for i in arr1 if i not in arr2]
        arr3.sort()
        lookup = {}
        res = []
        for i in arr1:
            if i in lookup:
                lookup[i] += 1
            else:
                lookup[i] = 1
        for i in arr2:
            for j in range(lookup[i]):
                res.append(i)
        return res + arr3

Explanation:

We need to sort arr1 using arr2. In other words, we can use arr2 to generate a new array.

The first step is to count how many element are there in arr1 for each element in arr2. Then we append each element in arr2 times it occurs in arr1 to our new array res. Lastly, we concatenate the rest of of arr1 and res together.