Given an array arr of N integers, the task is to replace each element of the array by its rank in the array. The rank of an element is defined as the distance between the element with the first element of the array when the array is arranged in ascending order. If two or more are same in the array then their rank is also the same as the rank of the first occurrence of the element. 
Example 1:
Input:
N = 6
arr = [20, 15, 26, 2, 98, 6]
Output:
4, 3, 5, 1, 6, 2
Explanation:
After sorting, array becomes {2,6,15,20,26,98}
Rank(2) = 1 (at index 0) 
Rank(6) = 2 (at index 1) 
Rank(15) = 3 (at index 2) 
Rank(20) = 4 (at index 3) and so on..
Example 2:
Input:
N = 4
arr = [2, 2, 1, 6]
Output:
2, 2, 1, 3
Explanation:
After sorting, array becomes {1, 2, 2, 6}
Rank(1) = 1 (at index 0) 
Rank(2) = 2 (at index 1) 
Rank(2) = 2 (at index 2) 
Rank(6) = 3 (at index 3)
Rank(6) = 3 because rank after 2 is 3 as rank 
of same element remains same and for next element 
increases by 1.
Your Task:
Complete the function int replaceWithRank(), which takes integer N  and an array of N integers as input and returns the list in which element at each position of original array is replaced by the rank of that element.
Expected Time Complexity: O(N * logN)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def replaceWithRank(self, N, arr):

        # Code here

Solutions:
import heapq

class Solution:

	def replaceWithRank(self, N, arr):
		newArray = list(arr)
		newArray.sort()
		ranks = {}
		rank = 1
		for index in range(len(newArray)):
			element = newArray[index]
			if element not in ranks:
				ranks[element] = rank
				rank += 1
		for index in range(len(arr)):
			element = arr[index]
			arr[index] = ranks[arr[index]]
		return arr


import heapq

class Solution:

	def replaceWithRank(self, N, arr):
		heap = []
		for i in range(N):
			heapq.heappush(heap, (arr[i], i))
		rank = 0
		prev = float('-inf')
		for i in range(N):
			(curr, index) = heapq.heappop(heap)
			if prev != curr:
				rank += 1
			arr[index] = rank
			prev = curr
		return arr


import bisect

class Solution:

	def replaceWithRank(self, N, arr):
		b = []
		for i in range(N):
			b.append((arr[i], i))
		b.sort()
		ans = [0] * N
		curr = 1
		for i in range(N):
			if i > 0 and b[i][0] != b[i - 1][0]:
				curr += 1
			ans[b[i][1]] = curr
		return ans


import heapq

class Solution:

	def replaceWithRank(self, N, arr):
		heap = []
		for i in range(N):
			heapq.heappush(heap, (arr[i], i))
		(curr, prev) = (1, None)
		while heap:
			top = heapq.heappop(heap)
			arr[top[1]] = curr
			if prev == top[0]:
				arr[top[1]] = curr - 1
			else:
				curr += 1
			prev = top[0]
		return arr


class Solution:

	def replaceWithRank(self, N, arr):
		import heapq
		(heap, dic, res) = ([], {}, [])
		for num in arr:
			heapq.heappush(heap, num)
		k = 1
		while len(heap) > 0:
			dic[heap[0]] = k
			c = heap[0]
			heapq.heappop(heap)
			if len(heap) > 0:
				if c != heap[0]:
					k += 1
		for i in range(N):
			res.append(dic[arr[i]])
		return res


class Solution:

	def replaceWithRank(self, n, arr):
		s = set()
		for i in range(n):
			s.add(arr[i])
		s = list(s)
		s.sort()
		d = dict()
		for i in range(len(s)):
			d[s[i]] = i + 1
		ans = []
		for i in arr:
			ans.append(d[i])
		return ans


class Solution:

	def replaceWithRank(self, N, arr):
		x = sorted(set(arr))
		d = {}
		for i in range(len(x)):
			d[x[i]] = i
		for i in range(len(arr)):
			arr[i] = d[arr[i]] + 1
		return arr


import copy

class Solution:

	def replaceWithRank(self, N, arr):
		dummy_copy = arr[:]
		temp = 1
		dummy_copy.sort()
		rank = {}
		for i in range(N):
			if rank.get(dummy_copy[i], 0) == 0:
				rank[dummy_copy[i]] = temp
				temp += 1
		for i in range(N):
			arr[i] = rank[arr[i]]
		return arr


from collections import *

class Solution:

	def replaceWithRank(self, N, arr):
		c = sorted(list(set(arr)))
		dic = defaultdict(int)
		k = 1
		for i in c:
			dic[i] = k
			k += 1
		return [dic[i] for i in arr]


class Solution:

	def replaceWithRank(self, N, arr):
		l = []
		for i in range(len(arr)):
			l.append((arr[i], i))
		l.sort()
		ans = [-1] * len(arr)
		rank = 1
		prev = l[0][0]
		for (i, j) in l:
			if prev == i:
				ans[j] = rank
			else:
				rank += 1
				ans[j] = rank
			prev = i
		return ans


class Solution:

	def ranker(self, nums):
		temp = {}
		j = 0
		for i in range(len(nums)):
			if nums[i] not in temp:
				temp[nums[i]] = j + 1
				j += 1
		return temp

	def replaceWithRank(self, N, arr):
		nums = sorted(arr)
		rank = self.ranker(nums)
		for i in range(len(arr)):
			arr[i] = rank[arr[i]]
		return arr


import heapq

class Solution:

	def replaceWithRank(self, N, arr):
		res = [0 for i in range(N)]
		l = []
		d = {}
		for i in range(N):
			heapq.heappush(l, (arr[i], i))
		count = 1
		while len(l) > 0:
			curr = heapq.heappop(l)
			if curr[0] not in d:
				res[curr[1]] = count
				count = count + 1
				d[curr[0]] = curr[1]
			else:
				res[curr[1]] = res[d[curr[0]]]
		return res


class Solution:

	def replaceWithRank(self, N, arr):
		s = 0
		from heapq import heappush, heappop
		l = []
		for i in range(N):
			heappush(l, [arr[i], i])
			s += 1
		ans = [0 for i in range(N)]
		s = 1
		prev = 10 ** 9
		while len(l):
			(val, ind) = heappop(l)
			if prev != val:
				ans[ind] = s
				s += 1
			else:
				ans[ind] = s - 1
			prev = val
		return ans


import heapq

class Solution:

	def replaceWithRank(self, N, arr):
		b = []
		c = []
		memo = {}
		rank = 1
		for i in arr:
			heapq.heappush(b, i)
		while len(b) > 0:
			y = heapq.heappop(b)
			if y not in memo:
				memo[y] = rank
				rank += 1
		for i in arr:
			c.append(memo[i])
		return c


class Solution:

	def replaceWithRank(self, N, arr):
		sorted_arr = sorted(arr)
		freq = {}
		rank = 1
		for i in range(N):
			if sorted_arr[i] not in freq:
				freq[sorted_arr[i]] = rank
				rank += 1
		res = []
		for i in range(N):
			res.append(freq[arr[i]])
		return res


class Solution:

	def replaceWithRank(self, N, arr):
		arr2 = list(arr)
		arr2.sort()
		d = {}
		rank = 1
		for i in range(N):
			k = arr2[i]
			if k not in d:
				d[k] = rank
				rank += 1
		for i in range(N):
			arr[i] = d[arr[i]]
		return arr


class Solution:

	def replaceWithRank(self, N, arr):
		c = arr.copy()
		arr.sort()
		d = {}
		index = 1
		for i in range(len(arr)):
			if arr[i] not in d:
				d[arr[i]] = index
				index += 1
		ans = []
		for i in c:
			ans.append(d[i])
		return ans


class Solution:

	def replaceWithRank(self, N, arr):
		s = sorted(arr)
		res = []
		d = {}
		count = 0
		for i in s:
			if i not in d:
				count += 1
				d[i] = count
		for i in arr:
			res.append(d[i])
		return res


class Solution:

	def replaceWithRank(self, N, arr):
		l = sorted(arr)
		count = 1
		d = {}
		ans = []
		for i in l:
			if i not in d:
				d[i] = count
				count += 1
		for i in arr:
			j = d[i]
			ans.append(j)
		return ans


import heapq

class Solution:

	def replaceWithRank(self, N, arr):
		n = len(arr)
		res = [-1 for _ in range(n)]
		hp = []
		for i in range(n):
			heapq.heappush(hp, (arr[i], i))
		prev = -9999999999999
		rank = 0
		while hp:
			(num, idx) = heapq.heappop(hp)
			if num == prev:
				res[idx] = rank
			else:
				rank += 1
				res[idx] = rank
				prev = num
		return res


import heapq

class Solution:

	def replaceWithRank(self, N, arr):
		heap = []
		for i in range(N):
			heapq.heappush(heap, (arr[i], i))
		rank = 0
		prev = None
		while heap:
			(ele, idx) = heapq.heappop(heap)
			if prev is None or prev == ele:
				arr[idx] = rank + 1
				prev = ele
				continue
			rank += 1
			arr[idx] = rank + 1
			prev = ele
		return arr


class Solution:

	def replaceWithRank(self, N, arr):
		mp = {}
		cpy = arr[:]
		cpy.sort()
		temp = 1
		for i in range(N):
			if cpy[i] not in mp:
				mp[cpy[i]] = temp
				temp += 1
		for i in range(N):
			cpy[i] = mp[arr[i]]
		return cpy


class Solution:

	def replaceWithRank(self, N, arr):
		mp = {}
		for i in range(N):
			if arr[i] not in mp.keys():
				mp[arr[i]] = 0
		tarr = list(mp.keys())
		tarr.sort()
		for i in range(len(tarr)):
			mp[tarr[i]] = i + 1
		for i in range(N):
			arr[i] = mp[arr[i]]
		return arr


import heapq

class Solution:

	def replaceWithRank(self, N, arr):
		heap = []
		for (i, n) in enumerate(arr):
			heapq.heappush(heap, (n, i))
		res = [None] * len(arr)
		(val, pos) = heapq.heappop(heap)
		prev = val
		rank = 1
		res[pos] = rank
		while heap:
			(val, pos) = heapq.heappop(heap)
			if val != prev:
				rank += 1
			res[pos] = rank
			prev = val
		return res


import heapq

class Solution:

	def replaceWithRank(self, N, arr):
		d = {}
		for i in range(len(arr)):
			if arr[i] in d.keys():
				d[arr[i]].append(i)
			else:
				d[arr[i]] = [i]
		hp = []
		for i in d.keys():
			hp.append(i)
		heapq.heapify(hp)
		rank = 1
		while len(hp) != 0:
			ele = heapq.heappop(hp)
			for j in range(len(d[ele])):
				arr[d[ele][j]] = rank
			rank += 1
		return arr


class Solution:

	def replaceWithRank(self, N, arr):
		lists = arr.copy()
		lists.sort()
		dct = {}
		cnt = 0
		for i in range(len(lists)):
			if lists[i] not in dct:
				dct[lists[i]] = cnt + 1
				cnt += 1
		for i in range(len(arr)):
			arr[i] = dct.get(arr[i])
		return arr


class Solution:

	def replaceWithRank(self, N, arr):
		d = dict()
		for i in range(N):
			temp = d.get(arr[i], list())
			d[arr[i]] = temp + [i]
		from heapq import heappop, heappush
		pq = []
		for (k, v) in d.items():
			heappush(pq, (k, v))
		res = [0 for _ in range(N)]
		cnt = 1
		while len(pq) > 0:
			cur = heappop(pq)
			c = cur[1]
			for i in c:
				res[i] = cnt
			cnt += 1
		return res


class Solution:

	def replaceWithRank(self, N, arr):
		a = sorted(arr)
		m = {}
		c = 0
		for i in range(N):
			if a[i] not in m:
				m[a[i]] = i + 1 + c
			else:
				c -= 1
		for i in range(N):
			arr[i] = m[arr[i]]
		return arr


class Solution:

	def replaceWithRank(self, N, arr):
		s = sorted(set(arr))
		d = {}
		for i in range(len(s)):
			d[s[i]] = i + 1
		li = []
		for i in arr:
			li.append(d[i])
		return li


import heapq

class Solution:

	def replaceWithRank(self, N, arr):
		hp = []
		for (i, val) in enumerate(arr):
			heapq.heappush(hp, (val, i))
		prev = float('-inf')
		cur = float('-inf')
		res = []
		c = 0
		while len(hp) > 0:
			(value, index) = heapq.heappop(hp)
			if value != prev:
				c += 1
			else:
				c = cur
			arr[index] = c
			prev = value
			cur = c
		return arr


import heapq as hp

class Solution:

	def replaceWithRank(self, N, arr):
		temp = list(set(arr))
		hp.heapify(temp)
		li = [hp.heappop(temp) for i in range(len(temp))]
		d = {}
		for i in range(0, len(li)):
			d[li[i]] = i + 1
		N = len(li)
		for i in range(0, N):
			d[li[i]] = i + 1
		temp = []
		for i in arr:
			temp.append(d[i])
		return temp


class Solution:

	def replaceWithRank(self, N, arr):
		k = sorted(list(set(arr)))
		N = len(k)
		dic = {}
		for i in range(N):
			dic[k[i]] = i + 1
		l = []
		for i in arr:
			l.append(dic[i])
		return l


class Solution:

	def replaceWithRank(self, N, arr):
		tem = [i for i in arr]
		tem = set(tem)
		tem = sorted(list(tem))
		x = 1
		d = {}
		for i in tem:
			if i not in d:
				d[i] = x
			x += 1
		ans = []
		for i in arr:
			ans.append(d[i])
		return ans


class Solution:

	def replaceWithRank(self, N, arr):
		b = arr[:]
		b.sort()
		c = 1
		m = {}
		for i in b:
			if i not in m:
				m[i] = c
				c += 1
		for i in range(N):
			arr[i] = m[arr[i]]
		return arr


class Solution:

	def replaceWithRank(self, N, arr):
		mp = {}
		rank = 1
		b = sorted(arr)
		for i in range(N):
			if b[i] not in mp:
				mp[b[i]] = rank
				rank += 1
		return [mp[val] for val in arr]