Relative Sort Array
Easy · Arrays & Hashing · Array · Hash Table · Sorting · Counting Sort
Problem
You are given two arrays arr1 and arr2. The values in arr2 are distinct, and every value of arr2 also occurs in arr1.
Reorder arr1 so that the values that appear in arr2 come first, in the same relative order as in arr2, with all copies of a value together. Values of arr1 that are not in arr2 go at the end, in increasing order. Return the reordered array.
Examples
Input: arr1 = [5,3,9,3,1,5,0], arr2 = [3,5] Output: [3,3,5,5,0,1,9]
The 3s then the 5s follow arr2's order; 0, 1 and 9 are left over and sorted.
Input: arr1 = [8,2,4], arr2 = [4,8,2] Output: [4,8,2]
Every value is ranked by arr2.
Input: arr1 = [7,6,7], arr2 = [7] Output: [7,7,6]
Both 7s go first and 6 is appended.
Constraints
- 1 <= len(arr1), len(arr2) <= 1000
- 0 <= arr1[i], arr2[i] <= 1000
- All values of arr2 are distinct
- Every arr2[i] occurs in arr1
Approaches
- Scan once per ranked value, then sort the rest — time O(n · m + n log n), space O(n)
Follow-up
If the values were not bounded, sort with the key (position in arr2, value), giving unranked values a position after every ranked one: O(n log n). The use cases check whether an array is already in this order (one pass over the keys), and apply the same ranking to task names, where a counting array by value is not available.
Related problems
Start free on Cariara · Coding problems · System design studio
