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.
Example 1:
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]
Example 2:
Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6] Output: [22,28,8,6,17,44]
Constraints:
1 <= arr1.length, arr2.length <= 10000 <= arr1[i], arr2[i] <= 1000arr2 are distinct.arr2[i] is in arr1.This approach uses a hash map (or dictionary) to count the occurrences of each element in arr1. Then, it constructs a new listby first adding elements in the order they appear in arr2 based on their count, and then adding remaining elements in sorted order.
This code creates a dictionary to count occurrences of elements present in arr2 and compiles a list of elements that are only in arr1.
Firstly, it iterates over arr1 to populate the dictionary and the extra elements list.
The function then iterates over arr2 and appends each number to the result list based on the count recorded in the dictionary.
Finally, the function appends the sorted extra elements to the result.
JavaScript
Time Complexity: O(n log n), dominated by the sorting of extra elements not in arr2.
Space Complexity: O(n), primarily due to the dictionary and list of extra elements.
Utilize a custom comparator function to sort arr1 according to the order defined in arr2, with arr1 elements not in arr2 sorted at the end.
The C++ solution employs an unordered_map to assign a rank based on the position of each element in arr2.
Using a lambda function in its custom comparator, this mapping enables arr1 to be reordered according to where each element appears in arr2, with non-mappable (extra) numbers sorted naturally afterward.
Java
Time Complexity: O(n log n), determined by the sort operation.
Space Complexity: O(n) for the rank map.
| Approach | Complexity |
|---|---|
| Counting Sort with HashMap | Time Complexity: O(n log n), dominated by the sorting of extra elements not in arr2. |
| Custom Comparator Sorting | Time Complexity: O(n log n), determined by the sort operation. |
Sort an Array - Leetcode 912 - Python • NeetCodeIO • 50,922 views views
Watch 9 more video solutions →Practice Relative Sort Array with our built-in code editor and test cases.
Practice on FleetCode