Relative Sort Array

Problem Description

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 do not appear in arr2 should be placed at the end of arr1 in ascending order.

Key Insights

• The elements in arr2 define the required order for sorting arr1.
• Elements in arr1 that are not in arr2 should be sorted and appended at the end of the result.
• Efficiently track the occurrences of each element in arr1 using a hash table (dictionary).
• Utilize sorting to handle elements not present in arr2.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the leftover elements in arr1. Space Complexity: O(n) for storing the counts of elements in arr1.

Solution

To solve this problem, we can utilize a hash table (dictionary) to count the occurrences of each element in arr1. We then iterate through arr2 to build the result array based on the defined order, using the counts from our hash table. Finally, we extract the remaining elements that are not in arr2, sort them, and append them to our result.

Code Solutions