The problem. You're given arr1 and arr2, where the values of arr2 are distinct and all appear in arr1. Sort arr1 so that its values follow the order of `arr2`, and put the values that don't appear in arr2 at the end, in ascending order.
arr1 = [2,3,1,3,2,4,6,7,9,2], arr2 = [2,1,4,3,9] -> [2,2,2,1,4,3,3,9,6,7]
arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6] -> [22,28,8,6,17,44]Sometimes the order a question wants isn't "smallest first": by frequency, by position in another list, by which concatenation is bigger. You don't need a new sorting algorithm for that — you need a new comparator, the function the built-in sort calls to decide which of two items goes first. The sort stays O(n log n); all the thinking goes into defining the order correctly.
Two ways to write one. A key function maps each item to something with the right natural order (a rank, a tuple), and the sort compares keys — Python's key=, Java's Comparator.comparing. A comparison function looks at two items and returns negative, zero or positive. Keys are simpler when they exist; comparisons handle orders that depend on both items at once, like Largest Number.
Give every value a key — its rank in arr2, or a number after all ranks — and sort by key.
function relativeSortArray(arr1, arr2) { const rank = new Map(arr2.map((v, i) => [v, i])); // where each value of arr2 comes const key = (v) => (rank.has(v) ? rank.get(v) : arr2.length + v); // the rest go after, ascending return [...arr1].sort((a, b) => key(a) - key(b));}Time O(n log n + m), space O(n + m) for n = arr1's length and m = arr2's.
The values are small (0 to 1000 on LeetCode), so count each value in arr1, then write out arr2's values in order, each as many times as counted, and finally every leftover value in ascending order.
function relativeSortArray(arr1, arr2) { const count = new Array(1001).fill(0); for (const x of arr1) count[x]++; const out = []; for (const v of arr2) while (count[v]-- > 0) out.push(v); // arr2's values first, in its order for (let v = 0; v <= 1000; v++) while (count[v]-- > 0) out.push(v); // then the rest, ascending return out;}Time O(n + k), space O(k) for values up to k = 1000. Faster, but only because the values are small.
arr2.length + v must exceed every rank, and keep leftovers in ascending order; both hold.