DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Relative Sort Array - Solution
Solutions and explanations
Link to Problem StatementView on GitHubWatch Video

Video Explanation

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        order = {ele: idx for idx, ele in enumerate(arr2)}
        
        def relative_key(num):
            if num in order:
                return (0, order[num])
            return (1, num)
        
        return sorted(arr1, key=relative_key)

Complexity Analysis

Here, n is size of the first array arr1 (array to be sorted).
m is size of the second array arr2 (defines relative order), m <= n.

  • Time Complexity: O(n log n)
    • Sorting: O(n log n) (dominant factor)
    • Construction of Ordering HashMap: O(m)
    • Overall: O(n log n + m) = O(n log n)
  • Space Complexity: O(n)
    • Ordering HashMap: O(m) space, as it stores index mapping for m elements.
    • Output Sorted List: O(n) space, as we are returning a new list with n elements.
    • Overall: O(n + m) = O(n)

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        order = {ele: idx for idx, ele in enumerate(arr2)}        
        return sorted(arr1, key=lambda x: (order.get(x, float("inf")), x))

Complexity Analysis

Here, n is size of the first array arr1 (array to be sorted).
m is size of the second array arr2 (defines relative order), m <= n.

  • Time Complexity: O(n log n)
    • Sorting: O(n log n) (dominant factor)
    • Construction of Ordering HashMap: O(m)
    • Overall: O(n log n + m) = O(n log n)
  • Space Complexity: O(n)
    • Ordering HashMap: O(m) space, as it stores index mapping for m elements.
    • Output Sorted List: O(n) space, as we are returning a new list with n elements.
    • Overall: O(n + m) = O(n)

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        freq_map = collections.Counter(arr1)
        res = []

        # Add elements in the order defined by arr2, and remove from the frequency map
        for num in arr2:    
            num_cnt = freq_map.pop(num, 0)
            res.extend([num] * num_cnt)
        
        # Add remaining elements in ascending order
        for key in sorted(freq_map):    
            cnt = freq_map[key]
            res.extend([key] * cnt)
        return res

Complexity Analysis

Here, n is size of the first array arr1 (array to be sorted).
m is size of the second array arr2 (defines relative order), m <= n.
k is the number of distinct remaining elements in arr1 which are not in arr2, so (k <= n - m).

  • Time Complexity: O(n + k log k)
    • Construction of Frequency Map: O(n)
    • Traversing arr2 and adding elements to the result: O(m + sum of counts) i.e. at most O(m + n)
    • Sorting and adding remaining elements: O(k log k + sum of remaining counts) i.e. at most O(k log k + n)
    • So, overall Time Complexity is O(n + m + k log k) = O(n + k log k) as m <= n.
  • Space Complexity: O(n + k) = O(n)
    • Frequency Map Space: O(n) in worst case.
    • Output Space: O(n), as we are returning a new array with n elements.
    • Auxiliary Space for sorting remaining elements: O(1) if done in-place, or O(k) if the sorting algorithm uses additional space.

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        max_num = max(arr1)
        count = [0] * (max_num + 1)
        for num in arr1:
            count[num] += 1
        
        res = []
        for num in arr2:
            res.extend([num] * count[num])
            count[num] = 0
        
        for num in range(max_num + 1):
            res.extend([num] * count[num])
        return res

Complexity Analysis

Here, n is the size of the first array arr1 (array to be sorted).
m is size of the second array arr2 (defines relative order), m <= n.
max_num is the maximum element in arr1.

  • Time Complexity: O(n + max_num)

    • Counting occurrences in arr1: O(n)
    • Traversing arr2 and adding elements to the result: O(m + n)
    • Traversing count array and adding remaining elements: O(max_num + n)
    • Overall: O(m + n + max_num) = O(n + max_num) = O(n), since max_num ≤ 1000

  • Space Complexity: O(n + max_num)

    • Count array: O(max_num + 1)
    • Output array: O(n)
    • Overall: O(n + max_num) = O(n), since max_num ≤ 1000