Relative Sort Array

easy array sorting hash map

Problem

Given arr1 and arr2 (distinct, every element of arr2 also in arr1), sort arr1 so elements appearing in arr2 come first in arr2's relative order, and any other elements come after in ascending order.

Inputarr1 = [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]

Map each arr2 value to its index; sort arr1 by (rank, value).

arr1

arr2

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

function relativeSortArray(arr1, arr2) {
  const rank = new Map();
  arr2.forEach((v, i) => rank.set(v, i));
  const INF = arr2.length;
  return arr1.slice().sort((a, b) => {
    const ra = rank.has(a) ? rank.get(a) : INF;
    const rb = rank.has(b) ? rank.get(b) : INF;
    return ra - rb || a - b;
  });
}

class Solution {
    public 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);
        final int INF = arr2.length;
        Integer[] boxed = Arrays.stream(arr1).boxed().toArray(Integer[]::new);
        Arrays.sort(boxed, (a, b) -> {
            int ra = rank.getOrDefault(a, INF);
            int rb = rank.getOrDefault(b, INF);
            return ra != rb ? ra - rb : a - b;
        });
        int[] out = new int[boxed.length];
        for (int i = 0; i < out.length; i++) out[i] = boxed[i];
        return out;
    }
}

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 INF = (int)arr2.size();
    auto out = arr1;
    sort(out.begin(), out.end(), [&](int a, int b) {
        int ra = rank.count(a) ? rank[a] : INF;
        int rb = rank.count(b) ? rank[b] : INF;
        return ra != rb ? ra < rb : a < b;
    });
    return out;
}

Explanation

We want arr1 sorted by a custom order: values that appear in arr2 come first in arr2's exact order, and everything else comes after in normal ascending order. The trick is to turn that rule into a sort key.

First we build a rank map from each value in arr2 to its position, e.g. arr2 = [2,1,4,3,9,6] gives 2→0, 1→1, 4→2, .... Any value not in arr2 gets the rank INF = len(arr2), pushing it to the back.

Then we sort arr1 by the pair (rank, value). The rank decides the main order; values sharing the same rank (the leftover ones, all at INF) fall back to sorting by their actual value ascending.

Example: arr1 = [2,3,1,3,2,4,6,7,9,2,19]. The values 7 and 19 are not in arr2, so they get rank INF and end up last in ascending order, while the rest follow arr2's order, producing [2,2,2,1,4,3,3,9,6,7,19].

One map lookup turns the relative-order requirement into a clean comparison, so an ordinary sort does all the work.

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