Relative Sorting — Asked in Google, Microsoft and Visa Interview

Problem Statement :

Given two arrays ‘ARR’ and ‘BRR’ of size ’N’ and ‘M’ respectively. Your task is to sort the elements of ‘ARR’ in such a way that the relative order among the elements will be the same as those are in ‘BRR’. For the elements not present in ‘BRR’, append them in the last in sorted order.

Note:

Elements of ‘BRR’ are non repeating.

Sample Input:

ARR = { 9, 5, 8, 4, 6, 5 } and BRR = { 8, 4, 5 }

Sample Output:

{ 8, 4, 5, 5, 6, 9 }

Approach :

Using a Map

• The idea is to maintain a map frequencyMap of the elements ARR, for finding the count of occurrences of BRR elements in ARR.
• Then, for each element of BRR, find its frequency by looking in frequencyMap. Say for any element B its frequency comes out to be A, then add B, A times in the RES array. Also erase the entry corresponding to B from the frequencyMap.
• After the above step, the frequencyMap contains those elements whose corresponding elements do not lie in BRR. As the map contains elements in sorted order. So we simply iterate the rest of frequencyMap elements, and add them, its frequency times in our RES array.

Time Complexity : O(N*log(N)+M*log(N))
Space Complexity : O(N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.