Relative Sort Array

Problem Statement

Given arr1 and arr2 (distinct values, all in arr1), sort arr1 so elements appear in the same order as arr2. Elements not in arr2 go at the end in ascending order.

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]

Approach

Build a rank map from arr2. Sort arr1 with a key of (rank, value): elements in arr2 use their rank; elements not present use a large rank so they sort after, and the secondary value key keeps those ascending.

Complexity

• Time: O(n log n)
• Space: O(n)

Solution Code

Python

def relativeSortArray(arr1, arr2):
    rank = {v: i for i, v in enumerate(arr2)}
    return sorted(arr1, key=lambda x: (rank.get(x, len(arr2)), x))

Java

int[] relativeSortArray(int[] arr1, int[] arr2) {
    Map<Integer, Integer> rank = new HashMap<>();
    for (int i = 0; i < arr2.length; i++) rank.put(arr2[i], i);
    Integer[] boxed = Arrays.stream(arr1).boxed().toArray(Integer[]::new);
    Arrays.sort(boxed, (a, b) -> {
        int ra = rank.getOrDefault(a, arr2.length + a);
        int rb = rank.getOrDefault(b, arr2.length + b);
        return Integer.compare(ra, rb);
    });
    int[] res = new int[boxed.length];
    for (int i = 0; i < res.length; i++) res[i] = boxed[i];
    return res;
}

C++

vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    unordered_map<int, int> rank;
    for (int i = 0; i < (int)arr2.size(); i++) rank[arr2[i]] = i;
    int big = arr2.size();
    sort(arr1.begin(), arr1.end(), [&](int a, int b){
        int ra = rank.count(a) ? rank[a] : big + a;
        int rb = rank.count(b) ? rank[b] : big + b;
        return ra < rb;
    });
    return arr1;
}

Key Takeaways

• A composite key (rank, value) handles both the custom and the fallback order.
• Give missing elements a rank that also encodes their value for ascending tie-break.
• Reference: LeetCode 1122 (Relative Sort Array).