<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>

def bucket_sort(arr: List[int], pv: int, is_neg: bool = False):
    grid = [[] for _ in range(10)]
    for n in arr:
        d = abs(n) // pv % 10
        grid[d].append(n)
    
    idx = 0
    if is_neg:
        for i in range(9, -1, -1):
            for n in grid[i]:
                arr[idx] = n
                idx += 1
    else:
        for i in range(10):
            for n in grid[i]:
                arr[idx] = n
                idx += 1

def radix_sort(arr: List[int]) -> List[int]:
    pos, neg, maxi, mini = [], [], -float("inf"), float("inf")
    for n in arr:
        if n >= 0:
            pos.append(n)
            maxi = max(maxi, n)
        else:
            neg.append(n)
            mini = min(mini, n)
    
    if pos:
        pv = 1
        l_pos = int(log10(maxi)) + 1 if maxi else 1
        for _ in range(l_pos):
            bucket_sort(pos, pv)
            pv *= 10
            
    if neg:
        pv = 1
        l_neg = int(log10(abs(mini))) + 1
        for _ in range(l_neg):
            bucket_sort(neg, pv, True)
            pv *= 10
    
    return neg + pos
        
class Solution(object):
    def arrayRankTransform(self, nums: List[int]) -> List[int]:
        arr = radix_sort(list(set(nums)))
        d = {}
        for i, x in enumerate(arr):
            d[x] = i + 1
        ans = []
        for n in nums: ans.append(d[n])
        return ans
36800