View Relative Sort Array on LeetCode
Statistics
Time Spent Coding
5 minutes
Time Complexity
O(n + m) - All of the elements from arr1 (n) and arr2 (m) must be visited, resulting in the O(n + m) time complexity.
Space Complexity
O(n + m) - In the worst case, all elements are unique from both input lists, resulting in the O(n + m) space complexity.
Runtime Beats
94.25% of other submissions
Memory Beats
59.20% of other sumbissions
Explanation
The comments explain the program
Data Structures Used
Hash Map (Dictionary) - A data structure that maps keys to their values. Each key may only appear once.
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
# Count the frequency of each number from arr1
dic = defaultdict(int)
for n in arr1:
dic[n] += 1
# Populate the result array with all elements in arr2 + their appearances from arr1
res = []
for n in arr2:
if n in dic:
res += [n] * dic.pop(n)
else:
res += n
# Populate the leftover array with all the numbers from arr1 that were not in arr2
leftover = []
for k,v in dic.items():
leftover += [k]*v
# Return the final result array combined with the sorted leftover array
return res + sorted(leftover)