Hashing: Given two arrays, sort first array according to the order of second array

Problem Statement:

You are given two arrays, you need to sort arr1 by the order of arr2.

Example:

Input: arr1 = [3, 2, 1, 1, 5] arr 2 = [1, 2, 3]

Output: arr = [1, 1, 2, 3, 5]

Solution Explanation:

We will create a freq array to count the number of elements in arr1 and increment the count.

Then for each element in arr2, add the element into the result array as many times of arr1, and remove the element from freq map.

Sort and place remaining elements from arr1

Time Complexity: O(nlogn)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_map>
using namespace std;


vector<int> solution(vector<int>& arr1, vector<int>& arr2) 
{
    unordered_map<int, int> freqMap;

    for (int num : arr1) 
    {
        freqMap[num]++;
    }

    vector<int> result(arr1.size());
    int index = 0;

    for (int num : arr2) 
    {
        if (freqMap.find(num) != freqMap.end()) 
        {
            int count = freqMap[num];

            for (int i = 0; i < count; i++) 
            {
                result[index++] = num;
            }

            freqMap.erase(num);
        }
    }

    vector<int> remaining;

    for (auto& entry : freqMap) 
    {
        remaining.push_back(entry.first);
    }

    sort(remaining.begin(), remaining.end());

    for (int num : remaining) 
    {
        int count = freqMap[num];
        while (count > 0) 
        {
            result[index++] = num;
            count--;
        }
    }

    return result;
}

int main()
{
    
    vector<int> arr1 = { 3, 2, 1, 1, 5};
    vector<int> arr2 = { 1, 2, 3 };

    vector<int> arr3 = solution(arr1, arr2);
    
    for (int i = 0; i < arr3.size(); i++) {
        cout << arr3[i] << " ";
    }
    
    cout << endl;
    return 0;
}

Output

1 1 2 3 5