Algorithm
Problem Name: 1122. Relative Sort Array
Problem Link: https://leetcode.com/problems/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 <= 10000 <= arr1[i], arr2[i] <= 1000- All the elements of
arr2are distinct. - Each
arr2[i]is inarr1.
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;
}
}
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]
#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)
}
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]
#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)
Input
arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output
[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 < int, int>();
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;
}
}
}
Input
arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output
[22,28,8,6,17,44]