1331. Rank Transform Of An Array

Problem Statement in English

You’re given an integer array arr. You need to transform the array into a rank array where each element is replaced by its rank.

The rank represents how large the element is. The rank has the following rules:

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

Return the rank array.

Approach

Essentially, the rank is the first position of the element in the sorted array. We can use a hashmap to store the ranks of the elements.

Then we can modify the original array to replace each element with its rank.

And we’re done!

Solution in Python

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        s = sorted(arr)
        hm = {}
        i = 1

        for v in s:
            if v not in hm:
                hm[v] = i
                i += 1

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

        return arr

Complexity

• Time: $O(n \log n)$
  Since we sort the array.

• Space: $O(n)$
  Since we use a hashmap to store the ranks of the elements.

And we are done.