Given two integer arrays A1[ ] and A2[ ] of size N and M respectively. Sort the first array A1[ ] such that all the relative positions of the elements in the first array are the same as the elements in the second array A2[ ].
See example for better understanding.
Note: If elements are repeated in the second array, consider their first occurance only.
Example 1:
Input:
N = 11 
M = 4
A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}
A2[] = {2, 1, 8, 3}
Output: 
2 2 1 1 8 8 3 5 6 7 9
Explanation: Array elements of A1[] are
sorted according to A2[]. So 2 comes first
then 1 comes, then comes 8, then finally 3
comes, now we append remaining elements in
sorted order.
Example 2:
Input:
N = 11 
M = 4
A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}
A2[] = {99, 22, 444, 56}
Output: 
1 1 2 2 3 5 6 7 8 8 9
Explanation: No A1[] elements are in A2[]
so we cannot sort A1[] according to A2[].
Hence we sort the elements in non-decreasing 
order.
Your Task:
You don't need to read input or print anything. Your task is to complete the function sortA1ByA2() which takes the array A1[ ], array A2[ ] and their respective size N and M as input parameters and returns the sorted array A1[ ] such that the relative positions of the elements in A1[ ] are same as the elements in A2[ ]. For the elements not present in A2[ ] but in A1[ ], it appends them at the last in increasing order. 
Expected Time Complexity: O(N * Log(N)).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N, M ≤ 10^{6}
1 ≤ A1[i], A2[i] ≤ 10^{6}

Difficulty: MEDIUM
Tags: String algorithms

Sorting

Data structures

Complete search
Skill types: Sorting

Data structures

Complete search
Expected Time Complexity: O(N * Log(N)).
Expected Auxiliary Space: O(N).

Starter code:
#User function Template for python3

class Solution:
    # A1[] : the input array-1
    # N : size of the array A1[]
    # A2[] : the input array-2
    # M : size of the array A2[]
    
    #Function to sort an array according to the other array.
    def relativeSort (self,A1, N, A2, M):
        # Your Code Here
    

Solutions:
class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = {}
		for i in A1:
			d[i] = d.get(i, 0) + 1
		ans = []
		flg = 0
		for i in A2:
			if i in d:
				ans.extend([i] * d[i])
				d[i] = 0
				flg = 1
		tmp = len(ans)
		for i in d:
			if d[i] != 0:
				ans.extend([i] * d[i])
		if flg == 0:
			return sorted(A1)
		else:
			ans[tmp:] = sorted(ans[tmp:])
			return ans


class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = {}
		for i in A1:
			d[i] = d.get(i, 0) + 1
		a1 = set(A1)
		a2 = set(A2)
		a = a1.intersection(a2)
		b = a1 - a
		B = []
		for i in b:
			B.extend([i] * d[i])
		B.sort()
		ret = []
		for i in A2:
			if i in a:
				a.remove(i)
				ret.extend([i] * d[i])
		ret.extend(B)
		return ret


from collections import Counter

class Solution:

	def relativeSort(self, A1, N, A2, M):
		c = Counter(A1)
		s = set(A1)
		ans = []
		for i in A2:
			if i in s:
				ans += [i] * c[i]
				s.remove(i)
		for i in sorted(list(s)):
			ans += [i] * c[i]
		return ans


from collections import Counter

class Solution:

	def relativeSort(self, A1, N, A2, M):
		hash_map = dict(Counter(A1))
		sorted_arr = []
		count = 0
		for i in A2:
			if i in hash_map:
				count = hash_map[i]
				for j in range(count):
					sorted_arr.append(i)
				del hash_map[i]
		for (i, j) in sorted(hash_map.items()):
			for k in range(j):
				sorted_arr.append(i)
		return sorted_arr


class Solution:

	def relativeSort(self, A1, N, A2, M):
		count = [0] * (max(A1) + 1)
		result = []
		for num in A1:
			count[num] += 1
		for num in A2:
			while count[num] > 0:
				result.append(num)
				count[num] -= 1
		for num in range(len(count)):
			while count[num] > 0:
				result.append(num)
				count[num] -= 1
		return result


from collections import defaultdict

class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = defaultdict(int)
		for i in A1:
			d[i] += 1
		ans = []
		for i in A2:
			if i in d:
				ans += [i] * d[i]
				del d[i]
		for (key, val) in sorted(d.items()):
			ans += [key] * val
		return ans


class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = {}
		for i in range(len(A1)):
			if A1[i] not in d:
				d[A1[i]] = 1
			else:
				d[A1[i]] += 1
		out = []
		for i in A2:
			if i in d:
				out.extend([i] * d[i])
				del d[i]
		for i in sorted(d):
			out.extend([i] * d[i])
		return out


from collections import OrderedDict

class Solution:

	def relativeSort(self, A1, N, A2, M):
		m = OrderedDict()
		ans = []
		for i in A1:
			if i not in m:
				m[i] = 1
			elif i in m:
				m[i] += 1
		for i in A2:
			if i in m:
				freq = m[i]
				while freq:
					freq -= 1
					ans.append(i)
				m[i] = 0
		m = OrderedDict(sorted(m.items()))
		for i in m:
			freq = m[i]
			while freq:
				ans.append(i)
				freq -= 1
			m[i] = 0
		return ans


from collections import Counter

class Solution:

	def relativeSort(self, A1, N, A2, M):
		counter = Counter(A1)
		result = []
		for num in A2:
			if num in counter:
				result.extend([num] * counter[num])
				del counter[num]
		remaining = []
		for (num, count) in counter.items():
			remaining.extend([num] * count)
		remaining.sort()
		result.extend(remaining)
		return result


from collections import Counter

class Solution:

	def relativeSort(self, A1, N, A2, M):
		counter = Counter(A1)
		result = []
		for num in A2:
			if num in counter:
				result.extend([num] * counter[num])
				del counter[num]
		remaining = sorted(counter.keys())
		for num in remaining:
			result.extend([num] * counter[num])
		return result


class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = {}
		for i in A1:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		ans = []
		an = []
		arr = set(A1) - set(A2)
		for i in arr:
			if i in d:
				an.extend([i] * d[i])
		for i in A2:
			if i in d:
				ans.extend([i] * d[i])
		ll = list(an)
		ll.sort()
		ans.extend(ll)
		return ans


from collections import OrderedDict

class Solution:

	def relativeSort(self, A1, N, A2, M):
		A1.sort()
		dic = OrderedDict()
		ans = []
		for i in range(N):
			if A1[i] not in dic:
				dic[A1[i]] = 1
			else:
				dic[A1[i]] += 1
		for i in range(M):
			if A2[i] in dic:
				count = dic[A2[i]]
				while count > 0:
					ans.append(A2[i])
					count -= 1
				del dic[A2[i]]
		for key in dic.keys():
			count = dic[key]
			while count > 0:
				ans.append(key)
				count -= 1
			dic[key] = count
		return ans


class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = {}
		for i in A1:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		l = []
		for i in A2:
			if i in d:
				for _ in range(d[i]):
					l += [i]
				del d[i]
		l1 = []
		for i in d:
			for j in range(d[i]):
				l1 += [i]
		l1.sort()
		l += l1
		return l


class Solution:

	def relativeSort(self, A1, N, A2, M, priority=None):
		sA1 = []
		sA2 = []
		if N == 0 or N == 1:
			return A1
		if priority == None:
			priority = {}
			for i in range(M):
				if A2[i] not in priority:
					priority[A2[i]] = len(priority)
		pivot = A1[0]
		if pivot in priority:
			for i in range(1, N):
				if A1[i] in priority:
					if priority[A1[i]] < priority[pivot]:
						sA1.append(A1[i])
					else:
						sA2.append(A1[i])
				else:
					sA2.append(A1[i])
		else:
			for i in range(1, N):
				if A1[i] in priority:
					sA1.append(A1[i])
				elif A1[i] < pivot:
					sA1.append(A1[i])
				else:
					sA2.append(A1[i])
		ob = Solution()
		r1 = ob.relativeSort(sA1, len(sA1), A2, M, priority)
		r1.append(pivot)
		r2 = ob.relativeSort(sA2, len(sA2), A2, M, priority)
		return r1 + r2


class Solution:

	def relativeSort(self, A1, N, A2, M):
		dic = {}
		li = []
		oli = []
		for i in range(M):
			dic[A2[i]] = 0
		for i in range(N):
			if A1[i] in dic:
				dic[A1[i]] += 1
			else:
				oli.append(A1[i])
		oli.sort()
		tmpli = []
		for i in range(M):
			tmpli.extend((A2[i] for j in range(dic[A2[i]])))
		li = li + tmpli
		li = li + oli
		return li


class Solution:

	def relativeSort(self, A1, N, A2, M):
		freq = {}
		for i in A1:
			if i in freq:
				freq[i] += 1
			else:
				freq[i] = 1
		sorted_A1 = []
		for i in A2:
			if i in freq:
				sorted_A1 += [i] * freq[i]
				del freq[i]
		remaining = []
		for (key, val) in freq.items():
			remaining += [key] * val
		sorted_A1 += sorted(remaining)
		return sorted_A1


class Solution:

	def relativeSort(self, A1, N, A2, M):
		hmap = {}
		for i in range(N):
			if A1[i] in hmap:
				hmap[A1[i]] += 1
			else:
				hmap[A1[i]] = 1
		ans = []
		for i in range(M):
			if A2[i] in hmap:
				ans += hmap[A2[i]] * [A2[i]]
				hmap[A2[i]] = 0
		myKeys = list(hmap.keys())
		myKeys.sort()
		for i in myKeys:
			if i != 0:
				ans += [i] * hmap[i]
		return ans


class Solution:

	def relativeSort(self, A1, N, A2, M):
		dic1 = {}
		for i in range(N):
			if A1[i] in dic1:
				dic1[A1[i]] += 1
			else:
				dic1[A1[i]] = 1
		A1.sort()
		a = []
		for i in range(M):
			if A2[i] in dic1:
				a = a + [A2[i]] * dic1[A2[i]]
				dic1.pop(A2[i])
		for i in A1:
			if i in dic1:
				a.append(i)
		return a


class Solution:

	def relativeSort(self, A1, N, A2, M):
		dict = {}
		l = []
		A1.sort()
		for i in A1:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		for i in A2:
			if i in dict:
				while dict[i] > 0:
					l.append(i)
					dict[i] -= 1
		for i in A1:
			if i in dict:
				while dict[i] > 0:
					l.append(i)
					dict[i] -= 1
		return l


from collections import Counter

class Solution:

	def relativeSort(self, A1, N, A2, M):
		c = Counter(A1)
		ans = []
		for i in A2:
			if i in c:
				for j in range(c[i]):
					ans.append(i)
				c[i] = 0
		temp = len(ans)
		for i in c:
			if c[i] != 0:
				for j in range(c[i]):
					ans.append(i)
		if len(ans) == 0:
			return A1.sort()
		else:
			ans[temp:] = sorted(ans[temp:])
		return ans


class Solution:

	def relativeSort(self, A1, N, A2, M):
		freq = {}
		for i in range(N):
			if A1[i] not in freq:
				freq[A1[i]] = 1
			else:
				freq[A1[i]] += 1
		result = []
		for j in range(M):
			if A2[j] in freq:
				result.extend([A2[j]] * freq[A2[j]])
				del freq[A2[j]]
		for elem in sorted(freq.keys()):
			result.extend([elem] * freq[elem])
		return result


class Solution:

	def relativeSort(self, A1, N, A2, M):
		freq = {}
		a = []
		temp = 0
		for i in A1:
			freq[i] = freq.get(i, 0) + 1
		for j in A2:
			if j in freq:
				a.extend(freq[j] * [j])
				freq[j] = 0
		l = len(a)
		b = []
		for i in freq:
			if freq[i] != 0:
				b.extend([i] * freq[i])
		a = a + sorted(b)
		return a


class Solution:

	def relativeSort(self, A1, N, A2, M):
		new_array = []
		new_array2 = []
		freq_hash = {}
		for value in A1:
			freq_hash[value] = freq_hash.get(value, 0) + 1
		for value in A2:
			if freq_hash.get(value, 0) != 0:
				for i in range(freq_hash[value]):
					new_array.append(value)
				freq_hash.pop(value)
		for key in freq_hash.keys():
			for i in range(freq_hash[key]):
				new_array2.append(key)
		new_array2.sort()
		new_array += new_array2
		return new_array
		return []


class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = {}
		for i in A1:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		ans = []
		flag = 0
		for i in A2:
			if i in d:
				ans.extend([i] * d[i])
				d[i] = 0
				flag = 1
		temp = len(ans)
		for i in d:
			if d[i] != 0:
				ans.extend([i] * d[i])
		if flag == 0:
			return sorted(A1)
		else:
			ans[temp:] = sorted(ans[temp:])
		return ans


from collections import defaultdict

class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = defaultdict(int)
		for i in range(N):
			d[A1[i]] += 1
		res = []
		for i in range(M):
			if d[A2[i]] > 0:
				while d[A2[i]] != 0:
					res.append(A2[i])
					d[A2[i]] -= 1
		A1.sort()
		for i in range(N):
			if d[A1[i]] != 0:
				res.append(A1[i])
		return res


class Solution:

	def relativeSort(self, A1, N, A2, M):

		def bin(lb, ub, n, l):
			if lb <= ub:
				mid = (lb + ub) // 2
				if l[mid] == n:
					return mid
				elif l[mid] < n:
					return bin(mid + 1, ub, n, l)
				else:
					return bin(lb, mid - 1, n, l)
			return -1
		A1.sort()
		l = []
		i = 0
		while i < M:
			r = bin(0, N - 1, A2[i], A1)
			if r == -1:
				i += 1
			else:
				l.append(A1.pop(r))
				N -= 1
		l.extend(A1)
		return l


class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = {}
		for i in A1:
			d[i] = d.get(i, 0) + 1
		l = set(A1)
		ans = []
		for i in A2:
			if i in l:
				ans += [i] * d[i]
				l.remove(i)
		for i in sorted(list(l)):
			ans += [i] * d[i]
		return ans


from collections import Counter as c

class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = c(A1)
		x = []
		for i in A2:
			if i not in d:
				continue
			x += [i] * d[i]
			d[i] = 0
		for i in sorted(d):
			x += [i] * d[i]
		return x


class Solution:

	def relativeSort(self, A1, N, A2, M):
		counts = {}
		for element in A1:
			if element in counts:
				counts[element] += 1
			else:
				counts[element] = 1
		sorted_A1 = []
		for element in A2:
			if element in counts:
				sorted_A1.extend([element] * counts[element])
				del counts[element]
		remaining_elements = sorted(counts.keys())
		for element in remaining_elements:
			sorted_A1.extend([element] * counts[element])
		return sorted_A1


from collections import Counter

class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = dict(Counter(A1))
		l = []
		l1 = []
		for i in A2:
			if i in d.keys():
				for j in range(d.get(i)):
					l.append(i)
				del d[i]
		for (x, y) in d.items():
			for j in range(y):
				l1.append(x)
		l1.sort()
		return l + l1


class Solution:

	def relativeSort(self, A1, N, A2, M):
		hashmap1 = {}
		for j in range(M):
			if A2[j] not in hashmap1:
				hashmap1[A2[j]] = 1
			else:
				hashmap1[A2[j]] += 1
		A1_dummy = []
		hashmap = {}
		n = 0
		for i in range(N):
			if A1[i] not in hashmap:
				hashmap[A1[i]] = 1
			else:
				hashmap[A1[i]] += 1
			if A1[i] not in hashmap1:
				A1_dummy.append(A1[i])
				n += 1
		result = []
		for j in range(M):
			if A2[j] in hashmap:
				result += [A2[j]] * hashmap[A2[j]]
				N -= hashmap[A2[j]]
		self.HeapSort(A1_dummy, n)
		result += A1_dummy
		return result

	def heapify(self, arr, n, i):
		smallest = i
		left = 2 * i + 1
		right = 2 * i + 2
		if left < n and arr[left] < arr[smallest]:
			smallest = left
		if right < n and arr[right] < arr[smallest]:
			smallest = right
		if smallest != i:
			(arr[i], arr[smallest]) = (arr[smallest], arr[i])
			self.heapify(arr, n, smallest)

	def buildHeap(self, arr, n):
		for i in range(n // 2 - 1, -1, -1):
			self.heapify(arr, n, i)
		return

	def HeapSort(self, arr, n):
		if n == 0:
			return arr
		res = []
		self.buildHeap(arr, n)
		while n > 1:
			(arr[0], arr[n - 1]) = (arr[n - 1], arr[0])
			res.append(arr.pop())
			n -= 1
			self.heapify(arr, n, 0)
		res.append(arr.pop())
		arr[:] = res[:]
		return


class Solution:

	def relativeSort(self, A1, N, A2, M):
		freq = {}
		for i in A1:
			freq[i] = freq.get(i, 0) + 1
		ans = []
		for i in A2:
			if i in freq:
				ans.extend([i] * freq[i])
				del freq[i]
		l = len(ans)
		for i in freq:
			ans.extend([i] * freq[i])
		ans[l:] = sorted(ans[l:])
		return ans
		return ans


from collections import Counter

class Solution:

	def relativeSort(self, A1, N, A2, M):
		freq = Counter(A1)
		ans = []
		for n in A2:
			ans.extend([n] * freq[n])
			freq[n] = 0
		keysList = list(freq.keys())
		keysList.sort()
		for n in keysList:
			if freq[n] != 0:
				ans.extend([n] * freq[n])
		return ans


import collections

class Solution:

	def relativeSort(self, A1, N, A2, M):
		ans = []
		d = collections.Counter(A1)
		for i in A2:
			for j in range(d[i]):
				ans.append(i)
			if i in d:
				d.pop(i)
		for i in sorted(d):
			ans.extend([i] * d[i])
		return ans


import collections

class Solution:

	def relativeSort(self, A1, N, A2, M):
		ans = []
		d = collections.Counter(A1)
		for i in A2:
			for j in range(d[i]):
				ans.append(i)
			if i in d:
				d.pop(i)
		ind = len(ans)
		for (i, j) in d.items():
			for k in range(j):
				ans.append(i)
		ans[ind:] = sorted(ans[ind:])
		return ans


from collections import Counter

class Solution:

	def relativeSort(self, arr1, N, arr2, M):
		res = []
		f = Counter(arr1)
		for e in arr2:
			res.extend([e] * f[e])
			f[e] = 0
		rem = list(sorted(filter(lambda x: f[x] != 0, f.keys())))
		for e in rem:
			res.extend([e] * f[e])
		return res


class Solution:

	def relativeSort(self, arr1, N, arr2, M):
		indexHash = {}

		def getPositionInArr2(a):
			if a in indexHash:
				return indexHash[a]
			return 10 ** 5 + a
		for (i, a) in enumerate(arr2):
			indexHash[a] = i
		return sorted(arr1, key=getPositionInArr2)


class Solution:

	def relativeSort(self, A1, N, A2, M):
		a1_counts = {}
		for x in A1:
			if x in a1_counts:
				a1_counts[x] += 1
			else:
				a1_counts[x] = 1
		relative_sort = []
		list_a1_only = []
		for y in A2:
			if y in a1_counts:
				relative_sort += [y] * a1_counts[y]
				del a1_counts[y]
		for (val, count) in a1_counts.items():
			list_a1_only += [val] * count
		relative_sort += sorted(list_a1_only)
		return relative_sort


class Solution:

	def relativeSort(self, A1, N, A2, M):
		A1_dict = {}
		for i in A1:
			if i not in A1_dict:
				A1_dict[i] = 1
			else:
				A1_dict[i] += 1
		k = 0
		for i in A2:
			if i in A1_dict:
				while A1_dict[i] > 0:
					A1[k] = i
					A1_dict[i] -= 1
					k += 1
		for key in sorted(A1_dict.keys()):
			if A1_dict[key] != 0:
				while A1_dict[key] > 0:
					A1[k] = key
					k += 1
					A1_dict[key] -= 1
		return A1


class Solution:

	def relativeSort(self, A1, N, A2, M):
		result2 = []
		result = []
		A1_dict = {}
		for i in range(len(A1)):
			if A1[i] not in A1_dict:
				A1_dict[A1[i]] = 1
			else:
				A1_dict[A1[i]] += 1
		for i in range(len(A2)):
			if A2[i] in A1_dict:
				v = A1_dict[A2[i]]
				for j in range(v):
					result.append(A2[i])
			A1_dict[A2[i]] = 0
		for (key, value) in A1_dict.items():
			if value != 0:
				v = A1_dict[key]
				for i in range(v):
					result2.append(key)
		result2.sort()
		for i in result2:
			result.append(i)
		return result


class Solution:

	def partition(self, arr, l, h):
		pivot = arr[h]
		j = l
		for i in range(l, h):
			if arr[i] < pivot:
				(arr[i], arr[j]) = (arr[j], arr[i])
				j += 1
		(arr[j], arr[h]) = (arr[h], arr[j])
		return j

	def quicksort(self, arr, l, h):
		if l < h:
			pi = self.partition(arr, l, h)
			self.quicksort(arr, l, pi - 1)
			self.quicksort(arr, pi + 1, h)

	def relativeSort(self, A1, N, A2, M):
		freq = {}
		for i in A1:
			freq[i] = freq.get(i, 0) + 1
		res = []
		for i in A2:
			if i in freq:
				res += [i] * freq[i]
				freq.pop(i)
		for i in sorted(freq.keys()):
			res += [i] * freq[i]
		return res


class Solution:

	def relativeSort(self, A1, N, A2, M):
		h = dict()
		for i in A1:
			if str(i) in h.keys():
				h[str(i)] += 1
			else:
				h.update({str(i): 1})
		s_arr = []
		for i in A2:
			flag = False
			try:
				for j in range(h[str(i)]):
					s_arr.append(i)
					flag = True
				if flag == False:
					s_arr.append(i)
				h[str(i)] = 0
			except Exception as e:
				continue
		x = []
		for i in h.keys():
			if h[i] != 0:
				for j in range(h[i]):
					x.append(int(i))
		x.sort()
		for i in x:
			s_arr.append(i)
		return s_arr


from collections import OrderedDict

class Solution:

	def leftindex(self, arr, n, x):
		start = 0
		end = n - 1
		mid = start + (end - start) // 2
		ans = -1
		while start <= mid:
			if arr[mid] == x:
				ans = mid
				end = mid - 1
			elif arr[mid] < x:
				start = mid + 1
			else:
				end = mid - 1
			mid = start + (end - start) // 2
		return ans

	def rightindex(self, arr, n, x):
		start = 0
		end = n - 1
		ans = -1
		mid = start + (end - start) // 2
		while start <= mid:
			if arr[mid] == x:
				ans = mid
				start = mid + 1
			elif arr[mid] < x:
				start = mid + 1
			else:
				end = mid - 1
			mid = start + (end - start) // 2
		return ans

	def relativeSort(self, A1, N, A2, M):
		table = OrderedDict()
		for i in A2:
			if i not in table:
				table[i] = 1
		A1.sort()
		arr = []
		count = 0
		for i in table:
			p = self.leftindex(A1, N, i)
			q = self.rightindex(A1, N, i)
			if p < 0 or q < 0:
				pass
			else:
				net = q - p + 1
				for j in range(net):
					arr.append(i)
					count += 1
		arr2 = []
		for i in A1:
			if i not in table:
				arr2.append(i)
		arr = arr + arr2
		return arr


class Solution:

	def relativeSort(self, A1, N, A2, M):
		mapper = {}
		for i in A1:
			if i not in mapper:
				mapper[i] = 1
			else:
				mapper[i] += 1
		j = 0
		for i in A2:
			if i in mapper:
				while mapper[i] > 0:
					A1[j] = i
					j += 1
					mapper[i] -= 1
				del mapper[i]
		for keys in sorted(mapper.keys()):
			while mapper[keys] > 0:
				A1[j] = keys
				j += 1
				mapper[keys] -= 1
		return A1


class Solution:

	def relativeSort(self, A1, N, A2, M):
		dict1 = {}
		dict2 = {}
		ans = []
		for i in A2:
			dict1[i] = True
		for i in A1:
			if i in dict2:
				dict2[i] += 1
			else:
				dict2[i] = 1
		A1.sort()
		for i in A2:
			if i in dict2:
				while dict2[i] > 0:
					ans.append(i)
					dict2[i] -= 1
		for i in A1:
			if i not in dict1:
				ans.append(i)
		return ans


class Solution:

	def relativeSort(self, A1, N, A2, M):
		dictin = {}
		l = []
		gq = []
		for i in A1:
			if i not in dictin:
				dictin[i] = 1
			else:
				dictin[i] += 1
		for i in range(M):
			if A2[i] in dictin:
				l += [A2[i]] * dictin[A2[i]]
				del dictin[A2[i]]
		li = list(dictin.keys())
		li.sort()
		for i in li:
			l += [i] * dictin[i]
		return l


from collections import Counter

class Solution:

	def relativeSort(self, A1, N, A2, M):
		A1.sort()
		count = Counter(A1)
		a2_set = set(A2)
		result = []
		for v in A2:
			occurences = count.get(v, 0)
			for _ in range(occurences):
				result.append(v)
		for v in A1:
			if v in a2_set:
				continue
			result.append(v)
		return result


class Solution:

	def relativeSort(self, A1, N, A2, M):
		k = []
		l = {}
		s = {}
		for i in A2:
			s[i] = 1
		for i in A1:
			if s.get(i, 0) == 1:
				l[i] = l.get(i, 0) + 1
			else:
				k.append(i)
		ans = []
		for i in A2:
			if l.get(i, -1) != -1:
				ans += [i] * l[i]
		k.sort()
		ans += k
		return ans


class Solution:

	def relativeSort(self, A1, N, A2, M):

		def bs(a, l, r, x):
			if r >= l:
				mid = l + (r - l) // 2
				if x == a[mid]:
					while mid - 1 >= 0 and a[mid - 1] == x:
						mid -= 1
					return mid
				elif a[mid] > x:
					return bs(a, l, mid - 1, x)
				else:
					return bs(a, mid + 1, r, x)
			return -1
		A1.sort()
		bb = list(set(A1).difference(set(A2)))
		c = []
		cc = []
		for i in range(len(A2)):
			ind = bs(A1, 0, len(A1) - 1, A2[i])
			if ind == -1:
				continue
			c.append(A1[ind])
			while ind + 1 < len(A1) and A1[ind + 1] == A1[ind]:
				c.append(A1[ind])
				ind += 1
		for i in range(len(bb)):
			ind = bs(A1, 0, len(A1) - 1, bb[i])
			if ind == -1:
				continue
			cc.append(A1[ind])
			while ind + 1 < len(A1) and A1[ind + 1] == A1[ind]:
				cc.append(A1[ind])
				ind += 1
		cc.sort()
		return c + cc


class Solution:

	def relativeSort(self, a, n, b, m):
		dic = {}
		for elm in a:
			if elm in dic:
				dic[elm] += 1
			else:
				dic[elm] = 1
		remaining = []
		ans = []
		for elm in b:
			if elm in dic:
				ans += [elm] * dic[elm]
				del dic[elm]
		for elm in dic:
			remaining += [elm] * dic[elm]
		remaining.sort()
		ans += remaining
		return ans


class Solution:

	def relativeSort(self, arr1, n, arr2, m):
		d = {}
		for i in arr1:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		res = []
		for i in arr2:
			if i in d:
				for j in range(d[i]):
					res.append(i)
				del d[i]
		rem_l = []
		for i in d:
			for j in range(d[i]):
				rem_l.append(i)
		rem_l.sort()
		res = res + rem_l
		return res


class Solution:

	def relativeSort(self, A1, N, A2, M):
		freq = {}
		for i in range(N):
			if A1[i] in freq:
				freq[A1[i]] += 1
			else:
				freq[A1[i]] = 1
		result = []
		for i in range(M):
			if A2[i] in freq:
				for j in range(freq[A2[i]]):
					result.append(A2[i])
				del freq[A2[i]]
		remaining = sorted(freq.keys())
		for i in range(len(remaining)):
			for j in range(freq[remaining[i]]):
				result.append(remaining[i])
		return result


from collections import OrderedDict

class Solution:

	def relativeSort(self, A1, N, A2, M):
		dict = {}
		ans = []
		for i in range(len(A1)):
			if A1[i] not in dict:
				dict[A1[i]] = 1
			else:
				dict[A1[i]] += 1
		for i in range(len(A2)):
			if A2[i] in dict:
				for j in range(dict[A2[i]]):
					ans.append(A2[i])
				del dict[A2[i]]
		dict = OrderedDict(sorted(dict.items()))
		for val in dict:
			for i in range(dict[val]):
				ans.append(val)
		return ans


class Solution:

	def relativeSort(self, A1, N, A2, M):
		from collections import Counter
		a = Counter(A1)
		ans = []
		rem = []
		for i in A2:
			if i in a:
				t = [i] * a[i]
				ans += t
				del a[i]
		for i in a:
			t = [i] * a[i]
			rem += t
		rem.sort()
		return ans + rem


from collections import Counter

class Solution:

	def relativeSort(self, A1, N, A2, M):
		f = Counter(A1)
		arr = []
		for e in A2:
			arr.extend([e] * f[e])
			f[e] = 0
		remaining = list(sorted(filter(lambda x: f[x] != 0, f.keys())))
		for e in remaining:
			arr.extend([e] * f[e])
		return arr


from collections import Counter

class Solution:

	def relativeSort(self, A1, N, A2, M):
		(a1, a2, n, m) = (A1, A2, N, M)
		s = set(a2)
		dic = Counter(a1)
		ans = []
		for i in a2:
			if i in s and i in dic:
				ans.extend([i for j in range(dic[i])])
				s.remove(i)
				del dic[i]
		for i in sorted(dic.keys()):
			ans.extend([i for j in range(dic[i])])
			del dic[i]
		return ans


from collections import *

class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = Counter(A1)
		l = []
		for i in A2:
			if i in d:
				l.extend([i] * d[i])
				del d[i]
		b = sorted(d.elements())
		res = l + b
		return res


class Solution:

	def relativeSort(self, A1, N, A2, M):
		d = {}
		for i in A1:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		l = []
		for i in A2:
			if i in d:
				l.extend([i] * d[i])
		s = set(A2)
		k = []
		for i in d:
			if i not in s:
				k.extend([i] * d[i])
		return l + sorted(k)


class Solution:

	def relativeSort(self, A1, N, A2, M):
		dict_freq = {}
		for x in A1:
			if x in dict_freq:
				dict_freq[x] += 1
			else:
				dict_freq[x] = 1
		result = []
		for x in A2:
			if x in dict_freq:
				freq = dict_freq[x]
				result += [x] * freq
				del dict_freq[x]
		remaining = sorted(dict_freq.keys())
		for x in remaining:
			freq = dict_freq[x]
			result += [x] * freq
		return result


class Solution:

	def relativeSort(self, A1, N, A2, M):
		z = []
		g = {}
		for i in A1:
			g.setdefault(i, 0)
			g[i] += 1
		for i in A2:
			try:
				z.extend([i] * g[i])
				del g[i]
			except:
				continue
		for i in sorted(list(g.keys())):
			z.extend([i] * g[i])
		return z


from collections import Counter

class Solution:

	def relativeSort(self, A1, N, A2, M):
		res = []
		d = Counter(A1)
		for j in A2:
			res.extend([j] * d[j])
			d[j] = 0
		remaining = list(sorted(filter(lambda x: d[x] != 0, d.keys())))
		for j in remaining:
			res.extend([j] * d[j])
		return res