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
Problem: 1122. Relative Sort Array
Problem Link:
Companies Asked: Google, Microsoft, Visa
Approach:
Define a hashmap say, counter.
For each ith element in arr, increase the count of appearance.
Define a vector answer.
For each ith element in brr, push ith element counter[brr[i]] times in answer.
Separate elements of arr that are not in brr.
Sort those separated elements and push them in answer.
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;
}
};