Relative Sort Array

How it works

Instead of manually placing elements, we can leverage the built-in sorting algorithm with a custom comparator. The key insight is to assign each element a "priority" based on its position in arr2.

Elements in arr2 get their index as priority (lower index = higher priority in the result). Elements not in arr2 get a large priority (like 1000 + value) so they sort after all arr2 elements, and among themselves they sort by their actual value.

Steps

1. Create a hash map that maps each element in arr2 to its index.
2. Define a custom comparator: for each element, its sort key is its index in arr2 if present, otherwise 1000 + element_value.
3. Sort arr1 using this custom comparator.
4. Return the sorted array.

This approach is elegant and leverages the natural sorting of arr2's indices to determine the final order.

Complexity

• Time complexity: O(n + m + n log n)
• Space complexity:
  • O(m) extra space.
  • O(n) space for the output list.

Where n is the size of the array arr1, and m is the size of the array arr2.

Things to watch for

Forgetting to Sort Elements Not in arr2

After placing all elements that appear in arr2 according to their relative order, the remaining elements must be sorted in ascending order and appended to the result. A common mistake is appending these leftover elements in their original order or in the order they were encountered, rather than sorting them first.

Modifying arr1 While Iterating Over It

In brute force approaches that mark processed elements (e.g., setting them to -1), care must be taken to handle the iteration correctly. Modifying the array while iterating can lead to skipped elements or incorrect indexing. Using a separate data structure like a hash map to track counts avoids this issue entirely.

from typing import List

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        index = {num: i for i, num in enumerate(arr2)}
        return sorted(arr1, key=lambda x: (index.get(x, 1000 + x)))

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> index;
        for (int i = 0; i < arr2.size(); i++) {
            index[arr2[i]] = i;
        }

        sort(arr1.begin(), arr1.end(), [&](int a, int b) {
            int ia = index.count(a) ? index[a] : 1000 + a;
            int ib = index.count(b) ? index[b] : 1000 + b;
            return ia < ib;
        });

        return arr1;
    }
};