Given an array with N distinct elements, convert the given array to a reduced form where all elements are in range from 0 to N-1. The order of elements is same, i.e., 0 is placed in place of smallest element, 1 is placed for second smallest element, and N-1 is placed for the largest element.
Note: You don't have to return anything. You just have to change the given array.
Example 1:
Input:
N = 3
Arr[] = {10, 40, 20}
Output: 0 2 1
Explanation: 10 is the least element so it
is replaced by 0. 40 is the largest
element so it is replaced by 3-1 = 2. And
20 is the 2nd smallest element so it is
replaced by 1.
Example 2:
Input:
N = 5
Arr[] = {5, 10, 40, 30, 20}
Output: 0 1 4 3 2
Explanation: As 5 is smallest element,
it's replaced by 0. Then 10 is 2nd
smallest element, so it's replaced by 1.
Then 20 is 3rd smallest element, so it's
replaced by 2. And so on.
Your Task:
You don't need to read input or print anything. Your task is to complete the function convert() which takes the array of integers arr and n as parameters and makes changes in the given array.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ Arr[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:



	def convert(self,arr, n):

		# code here

Solutions:
class Solution:

	def convert(self, arr, n):
		x = []
		y = []
		for i in arr:
			y.append(i)
		for i in arr:
			x.append(i)
		x.sort()
		mapp = {}
		for i in range(n):
			mapp[x[i]] = i
		arr.clear()
		for i in y:
			arr.append(mapp[i])


class Solution:

	def convert(self, arr, n):
		b = sorted(arr)
		for i in range(len(arr)):
			l = 0
			h = n - 1
			while l <= h:
				m = (l + h) // 2
				if b[m] == arr[i]:
					arr[i] = m
					break
				elif b[m] < arr[i]:
					l = m + 1
				else:
					h = m - 1


class Solution:

	def convert(self, arr, n):
		dict = {}
		new = []
		for i in range(n):
			new.append(arr[i])
		new.sort()
		for i in range(n):
			dict[new[i]] = i
		for i in range(n):
			arr[i] = dict[arr[i]]


class Solution:

	def convert(self, arr, n):
		sorted_arr = sorted(arr)
		index_map = {val: i for (i, val) in enumerate(sorted_arr)}
		for (i, val) in enumerate(arr):
			arr[i] = index_map[val]


class Solution:

	def convert(self, arr, n):
		temp = [arr[i] for i in range(n)]
		temp.sort()
		mpp = {}
		val = 0
		for i in range(n):
			mpp[temp[i]] = val
			val += 1
		for i in range(n):
			arr[i] = mpp[arr[i]]
		return arr


class Solution:

	def convert(self, arr, n):
		ls = []
		for (idx, num) in enumerate(arr):
			ls.append((num, idx))
		ls = sorted(ls)
		for i in range(len(ls)):
			arr[ls[i][1]] = i


class Solution:

	def convert(self, arr, n):
		sorted_array = sorted(arr)
		index_map = dict()
		for (idx, element) in enumerate(arr):
			index_map[element] = idx
		insert = 0
		for i in range(len(sorted_array)):
			num = sorted_array[i]
			idx = index_map[num]
			arr[idx] = insert
			insert += 1


class Solution:

	def convert(self, arr, n):
		new = arr[:]
		out = arr[:]
		new.sort()
		D = {}
		Index = 0
		for i in new:
			D[i] = Index
			Index += 1
		arr.clear()
		for i in out:
			arr.append(D.get(i))


class Solution:

	def convert(self, arr, n):
		x = []
		y = {}
		for ele in arr:
			x.append(ele)
		x.sort()
		counter = 0
		for ele in x:
			y[ele] = counter
			counter += 1
		for i in range(n):
			arr[i] = y[arr[i]]
		return arr


class Solution:

	def convert(self, arr, n):
		hmap = {}
		sorted_arr = sorted(arr)
		for i in range(n):
			hmap[sorted_arr[i]] = i
		res = []
		for i in range(n):
			res.append(hmap[arr[i]])
		arr[:] = res


class Solution:

	def convert(self, arr, n):
		arr2 = sorted(enumerate(arr), key=lambda v: v[1])
		for (i, (j, _)) in enumerate(arr2):
			arr[j] = i


class Solution:

	def convert(self, arr, n):
		p = arr.copy()
		p.sort()
		table = {}
		for i in range(n):
			if p[i] not in table:
				table[p[i]] = i
		for j in range(n):
			arr[j] = table[arr[j]]


class Solution:

	def binarysearch(self, arr1, ele, n):
		low = 0
		high = len(arr1) - 1
		while low <= high:
			mid = (low + high) // 2
			if arr1[mid] == ele:
				return mid - 1
			elif arr1[mid] > ele:
				high = mid - 1
			else:
				low = mid + 1
		return -1

	def convert(self, arr, n):
		arr1 = [0] * (n + 1)
		for i in range(n):
			arr1[i] = arr[i]
		arr1.sort()
		ans = []
		for i in range(n):
			z = ob.binarysearch(arr1, arr[i], n)
			ans.append(z)
		for i in range(n):
			arr[i] = ans[i]
		return ans


class Solution:

	def convert(self, arr, n):
		p = sorted(arr)
		dict_ = {}
		for index in range(n):
			dict_.update({p[index]: index})
		for index in range(n):
			arr[index] = dict_[arr[index]]


class Solution:

	def convert(self, arr, n):
		k = list()
		for i in arr:
			k.append(i)
		k.sort()
		d = dict()
		for i in range(n):
			d[k[i]] = i
		list1 = list()
		for i in arr:
			list1.append(d[i])
		for i in range(n):
			arr[i] = list1[i]


class Solution:

	def convert(self, a, n):
		arr = a.copy()
		arr.sort()
		dic = {}
		for i in range(n):
			dic[arr[i]] = i
		for i in range(n):
			a[i] = dic[a[i]]
		return a


class Solution:

	def convert(self, arr, n):
		copy = arr[:]
		copy.sort()
		d = {}
		for i in range(n):
			d[copy[i]] = i
		for i in range(n):
			arr[i] = d[arr[i]]


class Solution:

	def convert(self, a, n):
		ab = sorted(a)
		d = {}
		for i in range(n):
			d[ab[i]] = i
		for i in range(n):
			a[i] = d[a[i]]


class Solution:

	def convert(self, arr, n):
		l = arr[:]
		l.sort()
		hash = {}
		for i in range(n):
			hash[l[i]] = i
		for i in range(n):
			arr[i] = hash[arr[i]]
		return arr


class Solution:

	def convert(self, arr, n):
		res = arr.copy()
		res.sort()
		dic = {}
		for i in range(len(arr)):
			dic[res[i]] = i
		for (index, i) in enumerate(arr):
			val = dic[i]
			arr[index] = val
			index += 1


class Solution:

	def convert(self, arr, n):
		sorted_arr = {}
		for (i, num) in enumerate(sorted(arr)):
			sorted_arr[num] = i
		for (i, num) in enumerate(arr):
			arr[i] = sorted_arr[num]
		return arr


class Solution:

	def convert(self, arr, n):
		cp = sorted(arr)
		rec = {}
		for (i, x) in enumerate(cp):
			rec[x] = i
		for (i, x) in enumerate(arr):
			arr[i] = rec[x]


class Solution:

	def convert(self, arr, n):
		x = []
		y = []
		for i in arr:
			x.append(i)
		for i in arr:
			y.append(i)
		x.sort()
		d = {}
		for i in range(n):
			d[x[i]] = i
		arr.clear()
		for i in y:
			arr.append(d[i])
		return arr


from collections import OrderedDict

class Solution:

	def convert(self, arr, n):
		b = sorted(arr)
		d = OrderedDict()
		for i in range(len(arr)):
			d[b[i]] = i
		l = [0] * len(arr)
		for i in range(len(arr)):
			l[i] = d[arr[i]]
		arr[:] = l[:]


class Solution:

	def convert(self, arr, n):
		newArr = arr.copy()
		newArr.sort()
		sortDict = dict()
		for i in range(n):
			sortDict[newArr[i]] = i
		for i in range(n):
			arr[i] = sortDict[arr[i]]


from copy import deepcopy

class Solution:

	def convert(self, arr, n):
		s = deepcopy(arr)
		s.sort()
		temp = {}
		for i in range(n):
			temp[s[i]] = i
		for i in range(n):
			arr[i] = temp[arr[i]]


class Solution:

	def convert(self, arr, n):
		l = []
		m = []
		for i in arr:
			m.append(i)
		for i in arr:
			l.append(i)
		l.sort()
		map = {}
		for i in range(n):
			map[l[i]] = i
		arr.clear()
		for i in m:
			arr.append(map[i])


class Solution:

	def convert(self, arr, n):
		dic = {}
		t = arr.copy()
		t.sort()
		for i in range(n):
			dic[t[i]] = dic.get(t[i], 0)
			dic[t[i]] = i
		for i in range(n):
			arr[i] = dic[arr[i]]


class Solution:

	def convert(self, arr, n):
		sort_index = sorted(zip(arr, list(range(n))))
		for i in range(n):
			arr[sort_index[i][1]] = i


class Solution:

	def convert(self, arr, n):
		sort_index = (x[1] for x in sorted(zip(arr, list(range(n)))))
		for (order, i) in enumerate(sort_index):
			arr[i] = order


import heapq

class Solution:

	def convert(self, arr, n):
		pairArr = []
		for i in range(n):
			pairArr.append((arr[i], i))
		pairArr.sort()
		for j in range(n):
			arr[pairArr[j][1]] = j
		return arr


class Solution:

	def convert(self, a, n):
		copy = a[:]
		copy.sort()
		d = {}
		for i in range(n):
			d[copy[i]] = i
		for i in range(n):
			a[i] = d[a[i]]
		return a


class Solution:

	def convert(self, arr, n):
		indeices = {}
		count = 0
		sarr = arr.copy()
		for i in arr:
			indeices[i] = count
			count += 1
		sarr.sort()
		count = 0
		for i in sarr:
			arr[indeices[i]] = count
			count += 1


class Solution:

	def convert(self, arr, n):
		tmp = [] + arr
		tmp.sort()
		dic = {}
		for i in range(n):
			if tmp[i] not in dic:
				dic[tmp[i]] = i
		for i in range(n):
			arr[i] = dic[arr[i]]
		return arr


class Solution:

	def convert(self, arr, n):
		k = sorted(arr.copy())

		def binary(k, beg, end, search):
			while beg < end:
				mid = (beg + end) // 2
				if search < k[mid]:
					end = mid
				elif search == k[mid]:
					return mid
				else:
					beg = mid + 1
		for i in range(n):
			arr[i] = binary(k, 0, n, arr[i])


import numpy as np

class Solution:

	def convert(self, arr, n):
		indices = np.argsort(arr)
		for i in range(n):
			arr[indices[i]] = i


class Solution:

	def convert(self, arr, n):
		ans = arr
		tmp = arr.copy()
		tmp.sort()
		my_dict = dict()
		for i in range(len(tmp)):
			my_dict[tmp[i]] = i
		for i in range(len(arr)):
			ans[i] = my_dict[arr[i]]


class Solution:

	def convert(self, arr, n):
		k = arr.copy()
		k.sort()
		lis = {}
		ans = []
		for i in range(n):
			lis[k[i]] = i
		for i in arr:
			ans.append(lis[i])
		for i in range(n):
			arr[i] = ans[i]


class Solution:

	def convert(self, arr, n):
		k = sorted(arr)
		dic = {}
		for i in range(n):
			dic[k[i]] = i
		for i in range(n):
			arr[i] = dic[arr[i]]
		return arr


class Solution:

	def convert(self, arr, n):
		dic = dict()
		sorted_arr = sorted(arr)
		for i in range(n):
			dic[sorted_arr[i]] = i
		for i in range(n):
			arr[i] = dic[arr[i]]
		return arr


class Solution:

	def convert(self, arr, n):
		z = []
		for ele in arr:
			z.append(ele)
		z.sort()
		d = dict()
		for i in range(len(z)):
			d[z[i]] = i
		k = []
		for ele in arr:
			k.append(d[ele])
		while len(arr) != 0:
			arr.pop()
		for ele in k:
			arr.append(ele)
		return arr


class Solution:

	def convert(self, arr, n):
		v = []
		for i in range(n):
			v.append((arr[i], i))
		v.sort()
		for i in range(n):
			arr[v[i][1]] = i


class Solution:

	def convert(self, l, n):
		temp = l
		temp = sorted(temp)
		mp = dict()
		for i in range(len(l)):
			mp[temp[i]] = i
		for i in range(len(l)):
			l[i] = mp[l[i]]
		return l


class Solution:

	def convert(self, arr, n):
		a = [0] * n
		posarr = {}
		for i in range(n):
			posarr[arr[i]] = i
		arr.sort()
		for k in range(n):
			a[posarr[arr[k]]] = k
		for m in range(n):
			arr[m] = a[m]


class Solution:

	def convert(self, arr, n):
		l = arr[:]
		l.sort()
		y = {}
		for i in range(n):
			y[l[i]] = i
		for i in range(n):
			arr[i] = y[arr[i]]


class Solution:

	def convert(self, arr, n):
		a = sorted(arr)
		d = dict()
		li = []
		for i in range(n):
			d[a[i]] = i
		for i in range(n):
			arr[i] = d[arr[i]]
		return arr


class Solution:

	def convert(self, arr, n):
		a = sorted(arr)
		k = {val: i for (i, val) in enumerate(a)}
		for (i, val) in enumerate(arr):
			arr[i] = k[val]


class Solution:

	def convert(self, arr, n):
		list1 = sorted(enumerate(arr), key=lambda x: x[1])
		arr1 = [0] * n
		for i in range(n):
			arr1[list1[i][0]] = i
		arr[:] = arr1
		return arr


class Solution:

	def convert(self, arr, n):
		a = arr.copy()
		a.sort()
		red = {}
		for i in range(n):
			red[a[i]] = i
		for i in range(n):
			arr[i] = red[arr[i]]


class Solution:

	def convert(self, arr, n):
		t = arr.copy()
		d = dict()
		l = []
		t.sort()
		for i in range(n):
			if t[i] not in d.keys():
				d[t[i]] = i
		for j in range(n):
			if arr[j] in d.keys():
				arr[j] = d[arr[j]]


class Solution:

	def convert(self, arr, n):
		arr
		arr1 = arr.copy()
		arr2 = arr.copy()
		arr2.sort()
		l1 = []
		dict1 = {}
		for i in range(len(arr2)):
			if arr2[i] not in dict1:
				dict1[arr2[i]] = i
		for i in range(len(arr1)):
			arr[i] = dict1[arr1[i]]


class Solution:

	def convert(self, arr, n):
		srt = sorted(arr)
		d = {}
		for i in range(n):
			d[srt[i]] = i
		for i in range(n):
			arr[i] = d[arr[i]]


class Solution:

	def convert(self, arr, n):
		temp = arr.copy()
		temp.sort()
		dict1 = {}
		for x in range(len(temp)):
			dict1[temp[x]] = x
		for x in range(len(temp)):
			arr[x] = dict1[arr[x]]
		return arr


class Solution:

	def convert(self, arr, n):
		arr2 = sorted(arr)
		d = {}
		for i in range(n):
			d[arr2[i]] = i
		for i in range(n):
			arr[i] = d[arr[i]]
		return arr


class Solution:

	def convert(self, arr, n):
		list3 = []
		list3 = list3 + arr
		arr.sort()
		dic = {}
		for i in range(0, len(arr)):
			dic[arr[i]] = i
		x = 0
		for j in list3:
			dic[j]
			arr[x] = dic[j]
			x = x + 1


class Solution:

	def convert(self, arr, n):
		v = sorted(arr)
		d = {}
		for i in range(len(v)):
			d[v[i]] = i
		for i in range(len(arr)):
			arr[i] = d[arr[i]]
		return arr


class Solution:

	def convert(self, arr, n):
		v = sorted(arr)
		c = 0
		d = {}
		for i in v:
			d[i] = c
			c += 1
		for i in range(len(arr)):
			arr[i] = d[arr[i]]
		return arr
		print(d.values())


class Solution:

	def convert(self, arr, n):
		t = sorted(arr)
		dict = {}
		for i in range(n):
			dict.update({t[i]: i})
		for i in range(n):
			arr[i] = dict[arr[i]]


class Solution:

	def convert(self, arr, n):
		s_arr = sorted(arr)
		nim_dic = {x: y for (y, x) in enumerate(s_arr)}
		for i in range(0, n):
			arr[i] = nim_dic[arr[i]]


class Solution:

	def convert(self, arr, n):
		temp = []
		for i in range(n):
			temp.append(arr[i])
		temp.sort()
		d = {}
		for i in range(n):
			d[temp[i]] = i
		for i in range(n):
			arr[i] = d[arr[i]]


class Solution:

	def convert(self, arr, n):
		sorted_arr = sorted(arr)
		mapping = {}
		for (i, val) in enumerate(sorted_arr):
			mapping[val] = i
		for i in range(n):
			arr[i] = mapping[arr[i]]


class Solution:

	def convert(self, arr, n):
		temp = [arr[i] for i in range(n)]
		temp.sort()
		umap = {}
		val = 0
		for i in range(n):
			umap[temp[i]] = val
			val += 1
		for i in range(n):
			arr[i] = umap[arr[i]]


class Solution:

	def convert(self, arr, n):
		alpha = sorted(arr)
		x = {val: i for (i, val) in enumerate(alpha)}
		for (i, val) in enumerate(arr):
			arr[i] = x[val]
		return arr


class Solution:

	def convert(self, arr, n):
		dict1 = {}
		for i in range(len(arr)):
			dict1[arr[i]] = i
		arr.sort()
		d = []
		for i in arr:
			d.append(i)
		c = 0
		for i in d:
			x = dict1[i]
			arr[x] = c
			c += 1


class Solution:

	def convert(self, arr, n):
		lst = arr.copy()
		lst.sort()
		res = dict()
		for i in range(n):
			res[lst[i]] = i
		for j in range(n):
			arr[j] = res[arr[j]]
		return


class Solution:

	def convert(self, arr, n):
		a = [i for i in arr]
		a.sort()
		d = {}
		i = 0
		while i < n:
			d[a[i]] = i
			i = i + 1
		for j in range(n):
			arr[j] = d[arr[j]]


class Solution:

	def convert(self, arr, n):
		a = []
		for i in range(len(arr)):
			a.append((arr[i], i))
		a.sort(key=lambda x: x[0])
		for i in range(len(a)):
			ind = a[i][1]
			arr[ind] = i
		return arr


class Solution:

	def convert(self, arr, n):
		s = sorted(arr)
		hmap = {}
		for i in range(n):
			hmap[s[i]] = i
		for i in range(n):
			arr[i] = hmap[arr[i]]