The “Relative Sort Array” problem on Leetcode is a coding challenge that tests your skills in array manipulation and sorting algorithms. While the problem itself is not particularly difficult, it does require a solid understanding of how to work with lists in Python, as well as some creative problem-solving skills. This comprehensive article will break down the problem statement, explore multiple ways to solve the problem, and discuss the time and space complexities associated with each approach.

## Problem Description

Here is the problem description as per Leetcode:

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 don’t appear in `arr2`

should be placed at the end of `arr1`

in ascending order.

### Example:

```
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]
```

## Brute-Force Approach Using Nested Loops

The simplest approach to solve this problem is to use nested loops to iterate through both `arr1`

and `arr2`

, placing the elements from `arr1`

in the same order as they appear in `arr2`

.

Here’s how this would look in Python:

```
def relativeSortArray(arr1, arr2):
result = []
for num in arr2:
while num in arr1:
result.append(num)
arr1.remove(num)
arr1.sort()
return result + arr1
```

### Time Complexity:

The time complexity is O(n×m), where n is the length of `arr1`

and mm is the length of `arr2`

.

### Space Complexity:

The space complexity is O(n), as we are storing the result array.

## Using Counting Sort

A more efficient approach is to use counting sort to keep track of the frequency of each number in `arr1`

. This allows us to construct the sorted list in a single pass.

```
from collections import Counter
def relativeSortArray(arr1, arr2):
count = Counter(arr1)
result = []
for num in arr2:
result += [num] * count[num]
del count[num]
for num in sorted(count.keys()):
result += [num] * count[num]
return result
```

### Time Complexity:

The time complexity is O(nlogn) due to the sorting step for the remaining elements in `count`

.

### Space Complexity:

The space complexity is O(n) for storing the result and the count dictionary.

## Using Custom Sorting

Another approach is to use custom sorting with the help of Python’s built-in `sorted()`

function. We define our own comparison function based on the index values in `arr2`

.

```
def relativeSortArray(arr1, arr2):
index_map = {num: index for index, num in enumerate(arr2)}
def custom_sort(x):
return (index_map.get(x, len(arr2)), x)
return sorted(arr1, key=custom_sort)
```

### Time Complexity:

The time complexity is O(nlogn) due to the sorting operation.

### Space Complexity:

The space complexity is O(n) for storing the result and the index_map dictionary.

## Using Bucket Sort

We can also solve this problem using bucket sort, which is particularly useful when the range of numbers in `arr1`

is known and not too large.

```
def relativeSortArray(arr1, arr2):
bucket = [0] * 1001
result = []
for num in arr1:
bucket[num] += 1
for num in arr2:
result += [num] * bucket[num]
bucket[num] = 0
for num in range(1001):
if bucket[num] > 0:
result += [num] * bucket[num]
return result
```

### Time Complexity:

The time complexity is O(n), assuming the size of the bucket is constant.

### Space Complexity:

The space complexity is O(n) for storing the result and the bucket array.

## Conclusion

The “Relative Sort Array” problem is a fantastic exercise for honing your array manipulation and sorting skills. While the brute-force approach is straightforward to implement, it suffers from poor time complexity. On the other hand, optimized solutions like Counting Sort and Bucket Sort offer better performance but require a deeper understanding of sorting algorithms.