Relative Sort Array
Easy· counting sort· custom order
Problem
Sort arr1 so that values appearing in arr2 come first, in the same order as in arr2. Values not present in arr2 go at the end in ascending order. All values in arr2 are distinct and also appear in arr1.
Examples
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]
7 and 19 are not in arr2, so they trail in ascending order.
Input: arr1 = [5,1,8,3], arr2 = [8,5]
Output: [8,5,1,3]
Constraints
- • 1 <= arr1.length, arr2.length <= 1000
- • 0 <= arr1[i], arr2[i] <= 1000
Hints & approach
Hint 1
A custom comparator based on each value's position in arr2 works.
Hint 2
The values are small, so counting sort avoids comparisons entirely.
Approachtry the hints first
Because values are bounded by 1000, count occurrences of each value in arr1 with a frequency array. Walk arr2 and emit each value as many times as it was counted, zeroing its count. Then sweep the frequency array from 0 upward and emit whatever remains. This is a counting sort with a custom order for the first part.
Time O(n + m + V) with V = 1001 · Space O(V)