Coder's Cat

LeetCode: Relative Sort Array

2020-11-25

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 don’t 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]

Solution #1: Frequency Count

class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
map<int, int> counts;
vector<int> result(arr1.size(), 0);
for(auto i : arr1) {
auto it = counts.find(i);
it == counts.end() ? counts[i] = 1 : counts[i]++;
}
int idx = 0;
for(auto v: arr2) {
for(auto n = 0; n < counts[v]; n++)
result[idx++] = v;
counts[v] = 0;
}

//sort left elements
vector<int> left;
for(auto v: arr1) {
if(counts[v] > 0)
left.push_back(v);
}
sort(left.begin(), left.end());

//append them into final result
for(auto v: left) result[idx++] = v;
return result;
}
}

Solution #2: Sort with a custom compare function

Because arr2’s elements all are contained in arr1, we can build a rank based on the index of elements.

The true challenge is how to reorder the elements in arr1. To achieve this we need to custom a sort function base on these rules:

  1. If values in listed in arr2, compare based on the rank build based on arr2
  2. If value is not in arr2, it will be left in latter part of final result
  3. If two values are not listed in arr2, compare based on the values of them.
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
unordered_map<int, int> rank;
// build rank based on arr2
for (int i = 0; i < arr2.size(); ++i) {
rank[arr2[i]] = i;
}
sort(arr1.begin(), arr1.end(), [&](int x, int y) {
if(rank.count(x) && rank.count(y)) return rank[x] < rank[y]; // rule #1
else if(rank.count(x)) return true; // rule #2
else if(rank.count(y)) return false; // rule #2
else return x < y; // rule #3
});
return arr1;
}
};

Preparing for an interview? Check out this!

Join my Email List for more helpful insights, It's Free!😋