1
class Solution:
2
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
3
        # initialise a dictionary since we're going to want to count the occurences of each element in arr1
4
        dic = {}
5
        # this loop populates the dictionary with the number of occurences for each element
6
        for elem in arr1:
7
            if dic.get(elem) is None:
8
                dic[elem] = 1
9
            else:
10
                dic[elem] = dic[elem] + 1
11
        # initialise a new list to store the values which exist in both arr2 and arr1
12
        output = []
13
        # populate output with the elements multiplied by their occurences (e.g. [1]*2 = [1, 1])
14
        for elem in arr2:
15
            output += [elem] * dic[elem]
16
        # initialise a new list to store the elements which are in arr1 but not arr2
17
        extra_output = []
18
        # populate extra_output with these elements multiplied by their occurences.
19
        # Note: set(arr1)-set(arr2) provides us with the set of numbers which exist in arr1 but not in arr2
20
        for elem in set(arr1) - set(arr2):
21
            extra_output += [elem] * dic[elem]
22
        # return the first list and the sorted second list
23
        return output + sorted(extra_output)