LeetCode: Relative Sort Array

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:

If values in listed in arr2, compare based on the rank build based on arr2
If value is not in arr2, it will be left in latter part of final result
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 insights, It's Free!😋

← LeetCode: Remove Duplicate Node ... LeetCode: Reverse Words in a Str... →