Relative Sort Array

This problem can be approached using the Python built-in sorting function with a custom comparison method. The approach would be as follows:

1. Count the occurrence of each element in arr1 and store it in a dictionary.
2. For each element in arr2, add that element to the result array as many times as it occurs in arr1 (based on our count from step 1), and remove the element count from the dictionary.
3. After all elements from arr2 have been added to the result, there may be remaining elements in arr1 that weren’t in arr2. Add these to the result in ascending order.

Here is the Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from typing import List
from collections import Counter

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        count = Counter(arr1)
        result = []

        for num in arr2:
            result.extend([num]*count[num])
            del count[num]

        for num in sorted(count):
            result.extend([num]*count[num])

        return result

Let’s break it down:

• The Counter object count is created from arr1, counting the occurrences of each number in arr1.
• We iterate over each number num in arr2. We extend the result list by num repeated count[num] times. Then we delete the count of num from the count dictionary.
• After adding all numbers present in arr2 to the result list, some numbers may remain in count (those that were in arr1 but not in arr2). We sort the remaining numbers and add them to the result list. We repeat each number count[num] times.
• Finally, we return the result list.

This approach ensures that the relative ordering in arr2 is preserved, and any extra elements not present in arr2 are added in ascending order at the end.

Alternate Solution

1. Because 0 <= arr1[i], arr2[i] <= 1000, we use an array to count every element.
2. Go through every element in the second array, and update values of the first array based on the order in the second array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        cnt = [0] * 1001
        for n in arr1: 
            cnt[n] += 1
        i = 0
        for n in arr2:
            while cnt[n] > 0:
                arr1[i] = n
                i += 1
                cnt[n] -= 1
        for n in range(len(cnt)):
            while cnt[n] > 0:
                arr1[i] = n
                i += 1
                cnt[n] -= 1
        return arr1