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 & Try With Live Editor

Input

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

Output

x
+
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 & Try With Live Editor

Input

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

Output

x
+
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 & Try With Live Editor

Input

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

Output

x
+
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 < 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;
        }
    }
}
Copy The Code & Try With Live Editor

Input

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

Output

x
+
cmd
[22,28,8,6,17,44]
Advertisements

Demonstration


Previous
#1117 Leetcode Building H2O Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1123 Leetcode Lowest Common Ancestor of Deepest Leaves Solution in C, C++, Java, JavaScript, Python, C# Leetcode