Relative Sort Array Leetcode Solution

In this problem, we are given two arrays of positive integers. All elements of the second array are distinct and are present in the first array. However, the first array can contain duplicate elements or elements that are not in the second array.

We need to sort the first array and return it keeping the relative order of its elements the same as that in the second array. Elements that are not present in the second array should appear at the end of the array in a non-decreasing manner. The elements in the array will not exceed the value of 1000.

Table of Contents

Example

Array1 = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99}
Array2 = {5 , 6 , 12}

5 5 6 6 12 1 4 4 7 99

Explanation: The order of elements in the second array is 5,6 and 12. So, they appear first in the result array. The other elements are 1, 4, 4, 7, and 99 which are sorted in non-decreasing order.

Array1 = {5 , 4 , 3 , 2 , 1}
Array2 = {1 , 2 , 3 , 4 , 5}

1 2 3 4 5

Explanation: We again sort the first array such that its elements are now in a similar order as that in the second array.

Approach(Custom Comparator)

When we use any sorting method, we use comparisons between two values of an array to decide their relative order. For example, in bubble sort, we keep comparing two adjacent elements so that the smaller element can be brought ahead in the array. The definition of “smaller” comes from the magnitude or value of elements. In general, the ‘<‘ operator checks if the LHS value is less than the RHS value. Programming Languages allow us to modify these operators to be overloaded in desirable ways. This is what we will use here. Such programming techniques where we use different comparison methods to decide the ordering is called custom comparing and we achieve it using custom comparators.

We pass another argument in the sort function that enables us to compare the elements in any fashion we want to. In order to understand its general functioning, let us check the following code:

vector <int> a = {1 , 2 , 3 , 7 , 4};
sort(a.begin() , a.end() , [&](const int &first , const int &second){
    return first > second;
});

In the above code snippet, the comparator checks whether a value first should come before value second in an integer array. The comparator should return true if we want first to come before second. Otherwise, we return false. The above code is an illustration where we sort the array in decreasing order. Similarly, in Java, we use a Comparator() class to decide the order of two arguments passed to it. It performs a 3-way comparison by returning -1, 0, and 1. If the first argument is less than the second, it returns -1. Else if the first argument is greater than the second, it returns 1. 0, otherwise.

Algorithm

Initialize a hash map position<> to hash the indices of elements in the second array to their respective indices
Sort the first array, but with passing a comparator function(using lambda function in C++ or comparator<> interface in Java)
The comparator works on two values first and second as follows:
1. If position[first] and position[second] do not exist:
  1. We want the smaller element to come first, so return first < second
2. If position[first] doesn’t exist:
  1. We return false as first should come later in the array
3. If position[second] doesn’t exist:
  1. Return true
4. Return position[first] < position[second]
Print the result

Implementation of Relative Sort Array Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

vector<int> relativeSortArray(vector<int>& Array1 , vector<int>& Array2)
{
    unordered_map <int , int> position;

    for(int i = 0 ; i < Array2.size() ; i++)
        position[Array2[i]] = i;

    sort(Array1.begin() , Array1.end() , [&](const int &first , const int &second)
     {
         if(position.find(first) == position.end() && position.find(second) == position.end())
             return first < second;
         if(position.find(first) == position.end())
             return false;
         if(position.find(second) == position.end())
             return true;
         return position[first] < position[second];
     });

    return Array1;
}

int main()
{
    vector <int> a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99} , b = {5 , 6 , 12};
    a = relativeSortArray(a , b);
    for(int &element : a)
        cout << element << " ";
    return 0;
}

Java Program

import java.util.*;

class relative_sort
{
    public static void main(String args[])
    {
        int[] a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99};
        int[] b = {5 , 6 , 12};
        a = relativeSortArray(a , b);
        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }

    static int[] relativeSortArray(int[] Array1, int[] Array2) {
        Hashtable <Integer , Integer> position = new Hashtable<>();
        for(int i = 0 ; i < Array2.length ; i++)
            position.put(Array2[i] , i);

        Integer[] _Array1 = new Integer[Array1.length];
        for(int i = 0 ; i < _Array1.length ; i++)
            _Array1[i] = Array1[i];

        Arrays.sort(_Array1 , new Comparator<Integer>()
                    {
                        public int compare(Integer first , Integer second)
                        {
                            if(position.get(first) == null && position.get(second) == null)
                                return first - second;
                            if(position.get(first) == null)
                                return 1;
                            if(position.get(second) == null)
                                return -1;
                            return position.get(first) - position.get(second);
                        }
                    });

        for(int i = 0 ; i < Array1.length ; i++)
            Array1[i] = _Array1[i];
        return Array1;
    }
}

5 5 6 6 12 1 4 4 7 99

Complexity Analysis of Relative Sort Array Leetcode Solution

Time Complexity

O(max(NlogN, M)) where N = size of the first array and M = size of the second array. We run a single pass on the second array which takes O(M) time and sort the first array which takes O(NlogN) time assuming the comparison is performed in constant time.

Space Complexity

O(M) as we store the indices of elements of the second array in a hash map.

Approach(Counting Sort)

Lets assume Array1 = {1 , 2 , 2 , 2} and Array2 = {2 , 1}. Start traversing the second array. We see integer 2 first. If we knew there were 3 2’s we would have easily written these values in the Array1 starting from index 0. Then, we have integer 1 in Array2. Again, if we knew its frequency, we would have easily stored them after twos. In a similar way, we can store the frequencies of all the elements in Array1 and then run a single pass of Array2, re-writing the elements in Array1 according to their frequencies.

But even after that, we would be ignoring those elements which are present in Array1 but not in Array2. So, we run a loop from lower limit to upper limit checking for every element which has some frequency left and write it into Array1. Since we go up from the lower limit to the upper, we would be sorting these “extra” elements in a non-decreasing manner.