Leetcode # 1122. Relative Sort Array

Problem

https://leetcode.com/problems/relative-sort-array

Solution

M := len(arr1), K := n_not_in_arr2)

Time Complexity: O(O(M) + O(len(K) * log(K)))
Space Complexity: O(M)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
    order = []
    n_in_arr2 = {}

    for i, n in enumerate(arr2):
      order.append([n, 0])
      n_in_arr2[n] = i
    n_not_in_arr2 = []

    for n in arr1:
      if n in n_in_arr2:
        order[n_in_arr2[n]][1] += 1
      else:
        n_not_in_arr2.append(n)
  
    return [e[0] for e in order for i in range(e[1])] + sorted(n_not_in_arr2) # O(M) + O(len(K) * log(K))); M := len(arr1), K := n_not_in_arr2
    

Last Updated on 2024/06/11 by A1go