Rank Transform of an Array — LeetCode 1331 Python Solution

The problem

Given an array of integers arr, replace each element with its rank. The rank represents how large the element is.

Example

Input

arr = [40,10,20,30]

Output

[4,1,2,3]

Explanation

40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Python solution

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        t = sorted(set(arr))
        return [bisect_right(t, x) for x in arr]

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1331. Rank Transform of an Array is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems