Relative Sort Array Algorithm: Sort Array Based on Predefined Sequence

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]

Constraints:

• arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• Each arr2[i] is distinct.
• Each arr2[i] is in arr1.

Relative Sorting via Custom Sorting in O(NlogN) complexity

We can provide a customize sorting function (or comparator IComparator in Java) that allows us to compare the elements in the array. We first go through the second array and put the elements’ indices in the hash map, then in the comparator, if both numbers appear in the hash map, we compare their indices. Otherwise, the one in the second array comes first. If neither is in the second array, we compare their values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> data;
        for (int i = 0; i < arr2.size(); ++ i) {
            data[arr2[i]] = i;
        }
        sort(begin(arr1), end(arr1), [&](auto &a, auto &b) {
            bool aa = data.find(a) != data.end();
            bool bb = data.find(b) != data.end();
            if (aa && bb) {
                return data[a] < data[b];
            }
            if ((!aa) && (!bb)) {
                return a < b;
            }
            return aa;
        });
        return arr1;
    }
};

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> data;
        for (int i = 0; i < arr2.size(); ++ i) {
            data[arr2[i]] = i;
        }
        sort(begin(arr1), end(arr1), [&](auto &a, auto &b) {
            bool aa = data.find(a) != data.end();
            bool bb = data.find(b) != data.end();
            if (aa && bb) {
                return data[a] < data[b];
            }
            if ((!aa) && (!bb)) {
                return a < b;
            }
            return aa;
        });
        return arr1;
    }
};

This C++ code takes O(N) space and O(nlogN) to compute.

Relative Sorting via Bucket Counting

Another algorithm to do the relative sorting would be to count the numbers and put them in the hash maps (bucket counting). We first store the second array in the hash set, and iterate the first array to divide the numbers into two: the one in the second array, and the rest. Both group of numbers are counted.

Then, we first push those numbers to the result (we have the counter for each number). Then, we push the rest (again we have counters). The map in C++ is sorted by keys. Inserting elements to a map takes O(logN). And overall complexity is O(nlogN).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_set<int> data;
        for (const auto &n: arr2) {
            data.insert(n);
        }
        map<int, int> others;
        unordered_map<int, int> counter;
        for (const auto &n: arr1) {
            if (data.find(n) == data.end()) {
                others[n] ++;
            } else {
                counter[n] ++;
            }
        }
        vector<int> res;
        for (const auto &n: arr2) {
            for (int i = 0; i < counter[n]; ++ i) {
                res.push_back(n);
            }
        }
        for (auto it = others.begin(); it != others.end(); ++ it) {
            for (int i = 0; i < it->second; ++ i) {
                res.push_back(it->first);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_set<int> data;
        for (const auto &n: arr2) {
            data.insert(n);
        }
        map<int, int> others;
        unordered_map<int, int> counter;
        for (const auto &n: arr1) {
            if (data.find(n) == data.end()) {
                others[n] ++;
            } else {
                counter[n] ++;
            }
        }
        vector<int> res;
        for (const auto &n: arr2) {
            for (int i = 0; i < counter[n]; ++ i) {
                res.push_back(n);
            }
        }
        for (auto it = others.begin(); it != others.end(); ++ it) {
            for (int i = 0; i < it->second; ++ i) {
                res.push_back(it->first);
            }
        }
        return res;
    }
};

Improved O(N) relative sorting algorithm

Given the input range is strictly from 0 to 1000, we can do the counting and put them in those buckets. Then, the elements from second array are pushed to the result first.

Next, we go through all the buckets in ascending order, to put the rest (those who do not appear in the second array) to the result vector – as the keys are incrementing, so the values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        int counter[1001] = { 0 };
        for (const auto &n: arr1) {
            counter[n] ++;
        }        
        vector<int> res;
        for (const auto &n: arr2) {
            while (counter[n] -- > 0) {
                res.push_back(n);
            }
        }
        for (int i = 0; i < 1001; ++ i) {
            while (counter[i] -- > 0) {
                res.push_back(i);
            }
        }        
        return res;
    }
};

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        int counter[1001] = { 0 };
        for (const auto &n: arr1) {
            counter[n] ++;
        }        
        vector<int> res;
        for (const auto &n: arr2) {
            while (counter[n] -- > 0) {
                res.push_back(n);
            }
        }
        for (int i = 0; i < 1001; ++ i) {
            while (counter[i] -- > 0) {
                res.push_back(i);
            }
        }        
        return res;
    }
};

The above C++ relative sorting takes O(1) constant space and O(N) time.

–EOF (The Ultimate Computing & Technology Blog) —