1122. Relative Sort Array

class Solution {
 public:
  vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    vector<int> ans;
    ans.reserve(arr1.size());  // Reserve space for the result
    unordered_map<int, int> count;

    for (int a : arr1)
      ++count[a];

    for (int a : arr2) {
      while (count[a]-- > 0)
        ans.push_back(a);
      count.erase(a);  // Remove the element to avoid redundant processing
    }

    // Collect remaining elements
    vector<int> remaining;
    for (const auto& [num, cnt] : count) {
      for (int i = 0; i < cnt; ++i)
        remaining.push_back(num);
    }

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

    return ans;
  }
};