hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Relative Sort Array


  • Approach:

    1. Define a hashmap say, counter.

    2. For each ith element in arr, increase the count of appearance.

    3. Define a vector answer.

    4. For each ith element in brr, push ith element counter[brr[i]] times in answer.

    5. Separate elements of arr that are not in brr.

    6. Sort those separated elements and push them in answer.

    7. Return answer.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(N)


Code [C++]

class Solution {

public:

vector<int> relativeSortArray(vector<int>& arr, vector<int>& brr) {

unordered_map<int, int>mp;

int n = arr.size(), m = brr.size();

for(int i=0; i<n; i++){

mp[arr[i]]++;

}

vector<int>rest, ans;

for(int i=0; i<m; i++){

if(mp.find(brr[i]) != mp.end()){

for(int j=0; j<mp[brr[i]]; j++){

ans.push_back(brr[i]);

}

mp[brr[i]] = 0;

}

}

for(int i=0; i<n; i++){

if(mp[arr[i]] != 0) rest.push_back(arr[i]);

}

sort(rest.begin(), rest.end());

for(int i=0; i<rest.size(); i++) ans.push_back(rest[i]);

return ans;

}

};