Relative Sort Array - Leetcode Solution

Problem Statement:

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 same as in arr2. Elements in arr1 that does not appear in arr2 should be placed at the end of arr1 in ascending order.

Example:

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:

In order to solve this problem we can use bucket sort and hash-maps.

First, we will create a hash-map that will store the frequency of each element in arr1.

We will then iterate through arr2 and add the elements to the result array in the order in which they appear in arr2. For each element of arr2, we check the frequency of the element in the hash-map and add it to the result array that many times. We will then remove the element from the hash-map.

Next, we will iterate through the hash-map and add all the remaining elements to the result array. We can do this by iterating through the keys of the hash-map and adding the element to the result array as many times as its frequency.

Finally, we will return the result array.

Code:

Time Complexity: O(N + MlogM), where N is the length of arr1 and M is the length of arr2.

Space Complexity: O(N).

The space is allocated for the hash-map and the result array.

class Solution { public: vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) { unordered_map<int, int> freq; for(int i: arr1) { freq[i]++; } vector<int> result; for(int i: arr2) { int f = freq[i]; while(f--) { result.push_back(i); } freq.erase(i); } vector<int> remaining; for(auto itr = freq.begin(); itr != freq.end(); itr++) { int f = itr -> second; while(f--) { remaining.push_back(itr -> first); } } sort(remaining.begin(), remaining.end()); for(int i: remaining) { result.push_back(i); } return result; } };

1