<p>Given an array of integers&nbsp;<code>arr</code>, replace each element with its rank.</p>

<p>The rank represents how large the element is. The rank has the following rules:</p>

<ul>
	<li>Rank is an integer starting from 1.</li>
	<li>The larger the element, the larger the rank. If two elements are equal, their rank must be the same.</li>
	<li>Rank should be as small as possible.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [40,10,20,30]
<strong>Output:</strong> [4,1,2,3]
<strong>Explanation</strong>: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [100,100,100]
<strong>Output:</strong> [1,1,1]
<strong>Explanation</strong>: Same elements share the same rank.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [37,12,28,9,100,56,80,5,12]
<strong>Output:</strong> [5,3,4,2,8,6,7,1,3]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup>&nbsp;&lt;= arr[i] &lt;= 10<sup>9</sup></code></li>
</ul>

'''
integer arr-- replace each ele wit hits "rank"

define:
    rank: how large the element is
        - rank is integer from 1
        - the larger the lelement the larger the rank, 
        - 2 ele equal -> rank is the same
        - rank should be as small as possible


Constraints:
    1. 0 length array
    2. negative integers

largest - 1
2nd -2 
3rd biggest - 3 
...and so on

time: O(logn)

1. create a dictionary/map to save index and the value
2. run sort on it
3. use the map to return items back to where they are
    - we have the value as the key and the index as the value.
    - when you return items to where they are, swap them by their rank number

[40,10,20,30]

map:
    40: 0
    10: 1
    20: 2
    30: 3

[10, 20, 30, 40]

old array:
rank = 1
    10 --> 1
    check if n+1 != n if n+1 in range
        rank++
    newArr[1] = 1
    20 -> 2
    newArr[2] = 2
    30 -> 3
    newArr[3] = 3
    40 -> 0
    newArr[0] = 4

return newArr

Time:
O(n) to map the value and index
O(nlogn) to sort it
O(n) to iterate through new array to make it
time: 2n + nlogn -> nlogn

Space:
space: n


Psuedocode:

# nothing to process
if not array -> return array
rank = 1
dicti = {}
newArr = array.sorted()
for ind, value in enumerate(newArr):
    if value in dicti:
        continue
    dicti[value] = rank
    rank++

for i in range(len(array)):
    array[i] = dicti[array[i]]

return newArr

sort- 10, 20, 30, 30, 40
rank- 1, 2, 3, 4

10 -> 1
20 -> 2
30 -> 3
40 -> 4

iterate through original array [30, 40, 10, 20, 30]
    40 -> 0



'''
class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        if len(arr) == 0:
            return []
        rank = 1
        dicti = {}
        newArr = sorted(set(arr))

        for ind, value in enumerate(newArr):
            dicti[value] = rank
            rank += 1

        for i in range(len(arr)):
            arr[i] = dicti[arr[i]]

        return arr
34500