Relative Sort Array - Solution & Explanation
Problem Statement
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] <= 1000- All the elements of
arr2are distinct. - Each
arr2[i]is inarr1.
Approach Overview
Problem Overview: You receive two arrays: arr1 and arr2. All elements of arr2 are distinct and also appear in arr1. Reorder arr1 so elements appear in the same relative order as arr2. Any values not present in arr2 must be placed at the end in ascending order.
Approach 1: Counting Sort with HashMap (O(n + k) time, O(k) space)
This approach uses frequency counting. First iterate through arr1 and build a frequency map (or counting array since values are small). Then iterate through arr2 and append each value to the result as many times as its frequency indicates. Decrease the count each time you place a value. After processing all arr2 elements, collect the remaining numbers from the frequency structure and append them in sorted order.
The key insight: elements in arr2 define a priority order. Counting frequencies lets you output them without repeated searches or comparisons. Because the value range is limited, this behaves like counting sort. Time complexity is O(n + k) where n is the size of arr1 and k is the value range. Space complexity is O(k). This technique combines ideas from hash tables and counting sort.
Approach 2: Custom Comparator Sorting (O(n log n) time, O(1) extra space)
Another option is to sort arr1 using a custom comparator. Build a map from value → index representing each element's position in arr2. During sorting, if both elements exist in the map, compare their mapped indices to preserve arr2's order. If only one element exists in the map, prioritize it before elements not present in arr2. If neither element exists in the map, compare them normally so they appear in ascending order.
This method relies entirely on the language's built-in sorting algorithm. The comparator encodes the problem rules. Time complexity is O(n log n) due to sorting. Space complexity is O(m) for the index map where m is the size of arr2.
Recommended for interviews: The counting sort approach is usually the expected optimal solution. It runs in linear time and shows you recognize the bounded value range. The custom comparator solution is still acceptable and often easier to implement quickly, but it is less optimal because of the O(n log n) sorting step. Mentioning both demonstrates strong problem-solving depth.
Approach 1: Counting Sort with HashMap
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.
Code
Python
JavaScript
Complexity
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.
Approach 2: Custom Comparator Sorting
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.
Complexity
Time Complexity: O(n log n), determined by the sort operation.
Space Complexity: O(n) for the rank map.
Approach 3: Custom Sorting
First, we use a hash table pos to record the position of each element in array arr2. Then, we map each element in array arr1 to a tuple (pos.get(x, 1000 + x), x), and sort these tuples. Finally, we take out the second element of all tuples and return it.
The time complexity is O(n times log n + m), and the space complexity is O(n + m). Here, n and m are the lengths of arrays arr1 and arr2, respectively.
Approach 4: Counting Sort
Try this approach in the editor →Complexity Comparison
| 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. |
| Custom Sorting | — |
| Counting Sort | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Sort with Frequency Map | O(n + k) | O(k) | Best choice when element range is limited and you want linear time performance |
| Custom Comparator Sorting | O(n log n) | O(m) | Good when using built-in sorting utilities or when counting range assumptions are unknown |
Video Solution
Relative Sort Array - Leetcode 1122 - Python • NeetCodeIO • 11,929 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Relative Sort Array easy or hard?
How to solve Relative Sort Array in O(n)?
What is the best approach for Relative Sort Array?
Is Relative Sort Array asked at Google/Amazon/Meta?
What data structure is used in Relative Sort Array?
What is the time complexity of Relative Sort Array?
Relative Sort Array Python or Java solution approach
Ready to solve this problem?
Practice Relative Sort Array with our built-in code editor and test cases.
Practice on FleetCode