Relative Sort Array
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
