Modified: August 02 2024

Description:

Given two arrays, arr1 and arr2, where all elements in arr2 are distinct, as well as all elements in arr2 are in arr1.

Sort the elements of arr1 so that the ordering of items in arr1 is the same as arr2. Any element not in arr2 should be appended in ascending/increasing order at the end of the list.

Example: 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]

Answer:


class Solution:

    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        count_map = {}
        remaining = []
        result = []

        # initialize count map with relative order elements
        for num in arr2:
            # a dictionary update statement, pushing each value
            # into it as a key and a value of 0
            count_map[num] = 0

        # count occurances of elements in target array
        for num in arr1:
            if num in count_map:
                count_map[num] += 1
            else:
                remaining.append(num)  

        # sort remaining
        remaining.sort()

        # add elements per relative order
        # num has to be in square brackets, else it breaks
        for num in arr2:
            result.extend([num] * count_map[num])

		# add remaining elements
        result.extend(remaining)

        return result