Relative Sort Array

Difficulty: Easy | Acceptance: 75.20% | Paid: No Topics: Array, Hash Table, Sorting, Counting Sort

You are 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 do not appear in arr2 should be placed at the end of arr1 in ascending order.

• Examples
• Constraints
• Counting Sort
• Custom Sorting
• Hash Map + Sorting

Examples

Example 1:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,6,7]
Output: [2,2,2,1,4,3,3,6,7,9,19]
Explanation: [2,2,2,1,4,3,3,6,7,9,19] is the sorted array that follows the relative order of arr2.

Example 2:

Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output: [22,28,8,6,17,44]
Explanation: [22,28,8,6,17,44] is the sorted array that follows the relative order of arr2.

Constraints

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

Counting Sort

Intuition Since values are bounded (0 to 1000), we can use counting sort to track frequencies and build the result by following arr2’s order, then adding remaining elements in ascending order.

Steps

• Create a count array of size 1001 and count occurrences of each element in arr1
• Iterate through arr2, adding each element to result according to its count
• Iterate through the count array from 0 to 1000, adding any remaining elements in ascending order

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        count = [0] * 1001
        for num in arr1:
            count[num] += 1
        
        result = []
        for num in arr2:
            result.extend([num] * count[num])
            count[num] = 0
        
        for num in range(1001):
            result.extend([num] * count[num])
        
        return result

Complexity

• Time: O(n + m + k) where n = arr1.length, m = arr2.length, k = 1001
• Space: O(k) for the count array
• Notes: Optimal solution given the constraint that values are bounded by 1000

Custom Sorting

Intuition Create a custom comparator that sorts elements based on their index in arr2, with elements not in arr2 placed at the end sorted by value.

Steps

• Build a hash map mapping each element in arr2 to its index
• Sort arr1 using a custom comparator: elements in arr2 compare by their index, elements not in arr2 come after and compare by value

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        index_map = {num: i for i, num in enumerate(arr2)}
        
        def custom_sort(x):
            if x in index_map:
                return (0, index_map[x])
            return (1, x)
        
        return sorted(arr1, key=custom_sort)

Complexity

• Time: O(n log n) for sorting
• Space: O(n + m) for the result and index map
• Notes: More general approach but slower due to sorting overhead

Hash Map + Sorting

Intuition Use a hash map to count frequencies, build result following arr2 order, then sort and append remaining elements.

Steps

• Count frequency of each element in arr1 using a hash map
• Iterate through arr2, adding each element to result according to its frequency and removing from map
• Sort remaining keys and add them to result with their frequencies

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        from collections import Counter
        
        count = Counter(arr1)
        result = []
        
        for num in arr2:
            result.extend([num] * count[num])
            del count[num]
        
        remaining = sorted(count.keys())
        for num in remaining:
            result.extend([num] * count[num])
        
        return result

Complexity

• Time: O(n + m + r log r) where r is the number of unique remaining elements
• Space: O(n) for the hash map and result
• Notes: Flexible approach that works even without value bounds, but sorting remaining elements adds overhead