#1122
Relative Sort Array
Easy Counting sort
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Sort arr1 so its elements follow the order given by arr2. Elements not in arr2 go at the end in ascending order. Values are 0..1000.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: order arr1 by arr2's order, leftovers ascending at the end.
Why this works: count every value, write arr2's values in its order, then the rest from 0 to 1000.
Example: arr1 [2,3,1,3,2,4,6,7,9,2,19], arr2 [2,1,4,3,9,6]
2,2,2, 1, 4, 3,3, 9, 6, then 7, 19✦Hints open one at a time
Count every value in arr1.
Emit values in arr2's order first, then the leftovers from 0 to 1000.
↗Approach
Counting sort with a custom order: first walk arr2 and write each value count times, then walk 0..1000 for the rest.
</>Solution (Java)
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] count = new int[1001];
for (int x : arr1) count[x]++;
int i = 0;
for (int x : arr2) {
while (count[x]-- > 0) arr1[i++] = x; // arr2 order first
}
for (int x = 0; x <= 1000; x++) {
while (count[x]-- > 0) arr1[i++] = x; // leftovers ascending
}
return arr1;
}
}!Common mistake
Using a comparator with indexOf on arr2 for every comparison — O(m) per compare.
Complexity
- Time: O(n + m + 1000).
- Space: O(1001).
Topic: Sorting
🎬 Episodes 24–28: video coming soon