Leetcode – Relative Sort Array Solution

Spread the love

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(nlog⁡n) 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(nlog⁡n) 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.

Leave a Reply