## Algorithm

Problem Name: 1122. Relative Sort Array

Given two arrays `arr1` and `arr2`, the elements of `arr2` are distinct, and all elements in `arr2` are also in `arr1`.

Sort the elements of `arr1` such that the relative ordering of items in `arr1` are the same as in `arr2`. Elements that do not appear in `arr2` should be placed at the end of `arr1` in ascending order.

Example 1:

```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]
```

Example 2:

```Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output: [22,28,8,6,17,44]
```

Constraints:

• `1 <= arr1.length, arr2.length <= 1000`
• `0 <= arr1[i], arr2[i] <= 1000`
• All the elements of `arr2` are distinct.
• Each `arr2[i]` is in `arr1`.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] frequency = new int[1001];
for (int num : arr1) {
frequency[num]++;
}
int[] result = new int[arr1.length];
int idx = 0;
for (int num : arr2) {
while (frequency[num]-- > 0) {
result[idx++] = num;
}
}
for (int i = 0; i < 1001; i++) {
while (frequency[i]-- > 0) {
result[idx++] = i;
}
}
return result;
}
}
``````
Copy The Code &

Input

cmd
arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]

Output

cmd
[2,2,2,1,4,3,3,9,6,7,19]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const relativeSortArray = function(arr1, arr2) {
const hash = {}
const res = []
arr1.forEach(el => {
if(hash.hasOwnProperty(el)) hash[el] += 1
else hash[el] = 1
})
for(let i = 0, len = arr2.length; i < len; i++) {
res.push(...makeArr(arr2[i], hash[arr2[i]]))
delete hash[arr2[i]]
}
const keys = Object.keys(hash).sort((a, b) => a - b)
for(let i = 0, len = keys.length; i < len; i++) {
res.push(...makeArr(keys[i], hash[keys[i]]))
}
return res
};

function makeArr(el, num) {
return new Array(num).fill(el)
}
``````
Copy The Code &

Input

cmd
arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]

Output

cmd
[2,2,2,1,4,3,3,9,6,7,19]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
return sorted(arr1, key = lambda x: arr2.index(x) if x in arr2 else len(arr2) + x)
``````
Copy The Code &

Input

cmd
arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]

Output

cmd
[22,28,8,6,17,44]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _1122_RelativeSortArray
{
public int[] RelativeSortArray(int[] arr1, int[] arr2)
{
var counts = new Dictionary();
foreach (var num in arr1)
{
if (counts.ContainsKey(num))
counts[num]++;
else
counts[num] = 1;
}

var index = 0;
foreach (var num in arr2)
{
var count = counts[num];
while (count > 0)
{
arr1[index++] = num;
count--;
}
counts.Remove(num);
}

foreach (var key in counts.Keys.OrderBy(num => num))
{
var count = counts[key];
while (count > 0)
{
arr1[index++] = key;
count--;
}
}

return arr1;
}
}
}
``````
Copy The Code &

Input

cmd
arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]

Output

cmd
[22,28,8,6,17,44]