1122. Relative Sort Array LeetCode Solution

In this guide, you will get 1122. Relative Sort Array LeetCode Solution with the best time and space complexity. The solution to Relative Sort Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Relative Sort Array solution in C++
Relative Sort Array solution in Java
Relative Sort Array solution in Python
Additional Resources

1122. Relative Sort Array LeetCode Solution image

Problem Statement of 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.

Complexity Analysis

Time Complexity:
Space Complexity:

1122. Relative Sort Array LeetCode Solution in C++

class Solution {
 public:
  vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    vector<int> ans;
    vector<int> count(1001);

    for (int a : arr1)
      ++count[a];

    for (int a : arr2)
      while (count[a]-- > 0)
        ans.push_back(a);

    for (int num = 0; num < 1001; ++num)
      while (count[num]-- > 0)
        ans.push_back(num);

    return ans;
  }
};
/* code provided by PROGIEZ */

1122. Relative Sort Array LeetCode Solution in Java

class Solution {
  public int[] relativeSortArray(int[] arr1, int[] arr2) {
    int[] ans = new int[arr1.length];
    int[] count = new int[1001];
    int i = 0;

    for (int a : arr1)
      ++count[a];

    for (int a : arr2)
      while (count[a]-- > 0)
        ans[i++] = a;

    for (int num = 0; num < 1001; ++num)
      while (count[num]-- > 0)
        ans[i++] = num;

    return ans;
  }
}
// code provided by PROGIEZ

1122. Relative Sort Array LeetCode Solution in Python

class Solution:
  def relativeSortArray(self, arr1: list[int], arr2: list[int]) -> list[int]:
    ans = []
    count = [0] * 1001

    for a in arr1:
      count[a] += 1

    for a in arr2:
      while count[a] > 0:
        ans.append(a)
        count[a] -= 1

    for num in range(1001):
      for _ in range(count[num]):
        ans.append(num)

    return ans
 # code by PROGIEZ