Code Implementation

class Solution:
    def relativeSortArray(self, arr1, arr2):
        from collections import Counter
        count = Counter(arr1)
        result = []
        # Add elements in arr2 order
        for num in arr2:
            result.extend([num] * count[num])
            count[num] = 0
        # Add remaining elements sorted
        leftovers = []
        for num in count:
            if count[num] > 0:
                leftovers.extend([num] * count[num])
        result.extend(sorted(leftovers))
        return result
      

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> count;
        for (int n : arr1) count[n]++;
        vector<int> result;
        // Add elements in arr2 order
        for (int n : arr2) {
            for (int i = 0; i < count[n]; ++i) result.push_back(n);
            count[n] = 0;
        }
        // Add remaining elements sorted
        vector<int> leftovers;
        for (auto& it : count) {
            for (int i = 0; i < it.second; ++i) leftovers.push_back(it.first);
        }
        sort(leftovers.begin(), leftovers.end());
        result.insert(result.end(), leftovers.begin(), leftovers.end());
        return result;
    }
};
      

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int n : arr1) count.put(n, count.getOrDefault(n, 0) + 1);
        List<Integer> result = new ArrayList<>();
        // Add elements in arr2 order
        for (int n : arr2) {
            for (int i = 0; i < count.getOrDefault(n, 0); ++i) result.add(n);
            count.put(n, 0);
        }
        // Add remaining elements sorted
        List<Integer> leftovers = new ArrayList<>();
        for (int n : count.keySet()) {
            int c = count.get(n);
            for (int i = 0; i < c; ++i) leftovers.add(n);
        }
        Collections.sort(leftovers);
        result.addAll(leftovers);
        // Convert to array
        int[] resArr = new int[result.size()];
        for (int i = 0; i < result.size(); ++i) resArr[i] = result.get(i);
        return resArr;
    }
}
      

var relativeSortArray = function(arr1, arr2) {
    let count = {};
    for (let n of arr1) count[n] = (count[n] || 0) + 1;
    let result = [];
    // Add elements in arr2 order
    for (let n of arr2) {
        for (let i = 0; i < (count[n] || 0); ++i) result.push(n);
        count[n] = 0;
    }
    // Add remaining elements sorted
    let leftovers = [];
    for (let n in count) {
        for (let i = 0; i < count[n]; ++i) leftovers.push(Number(n));
    }
    leftovers.sort((a, b) => a - b);
    result = result.concat(leftovers);
    return result;
};
      

Problem Description

You are given two arrays: arr1 and arr2. The task is to sort arr1 such that the relative ordering of items in arr1 matches the order given in arr2. Elements of arr1 that are not present in arr2 should be placed at the end of arr1 in ascending order.

• Every element in arr2 is unique and appears in arr1.
• Elements not in arr2 can appear anywhere in arr1 and should be sorted at the end.
• All elements from arr1 must be used exactly once in the output.
• There is always one valid solution.

Thought Process

The core challenge is to reorder arr1 so that elements present in arr2 maintain the same order as in arr2, while the rest are sorted. A brute-force approach could repeatedly scan arr1 for each value in arr2, but this is inefficient. Optimally, we want a way to quickly count and retrieve values in the desired order.

The key insight is to use a counting structure (like a hash map) to record how many times each number appears in arr1. Then, for each value in arr2, we can append that number the correct number of times, and finally sort and append the leftovers.

Solution Approach

• Step 1: Count the frequency of each element in arr1 using a hash map or counter.
• Step 2: For every element in arr2, append that element to the result as many times as it appears in arr1. After adding, set its count to zero to mark it as used.
• Step 3: For all remaining elements (those not in arr2), collect them from the counter, sort them in ascending order, and append them to the result.
• Step 4: Return the result array, which now satisfies the required relative order and sorting.

We use a hash map (dictionary) for counting because it allows O(1) lookups and updates, making the process efficient even for large arrays.

Example Walkthrough

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]

1. Count frequencies in arr1: 2 appears 3 times, 3 appears 2 times, 1 appears 1 time, 4 appears 1 time, 6 appears 1 time, 7 appears 1 time, 9 appears 1 time, 19 appears 1 time.
2. Go through arr2:
   • 2: add three 2's → result = [2,2,2]
   • 1: add one 1 → result = [2,2,2,1]
   • 4: add one 4 → result = [2,2,2,1,4]
   • 3: add two 3's → result = [2,2,2,1,4,3,3]
   • 9: add one 9 → result = [2,2,2,1,4,3,3,9]
   • 6: add one 6 → result = [2,2,2,1,4,3,3,9,6]
3. Leftovers: 7 and 19 (not in arr2), sort them: [7, 19]
4. Final result: [2,2,2,1,4,3,3,9,6,7,19]

Time and Space Complexity

• Brute-force approach: For each element in arr2, scan arr1 to collect matches (O(mn), where m = len(arr2), n = len(arr1)). Sorting leftovers adds O(k log k).
• Optimized approach:
  • Counting frequencies: O(n)
  • Processing arr2: O(m)
  • Sorting leftovers: O(k log k), where k is the number of elements not in arr2
  • Total: O(n + k log k)
  • Space: O(n) for the counter and output array

The optimized approach is much faster and uses reasonable extra space.

Summary

This problem is elegantly solved by counting occurrences and then reconstructing the array in the desired order. Using a hash map for counting ensures efficient lookups and insertions. The two-phase process—first placing elements by arr2's order, then sorting and appending the rest—makes the solution both intuitive and efficient, even for large inputs.