# 1331. Rank Transform of an Array

## Description

Given an array of integers arr, replace each element with 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.

Example 1:

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.

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.


Example 3:

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


Constraints:

• 0 <= arr.length <= 105
• -109 <= arr[i] <= 109

## Solutions

• class Solution {
public int[] arrayRankTransform(int[] arr) {
int n = arr.length;
int[] t = arr.clone();
Arrays.sort(t);
int m = 0;
for (int i = 0; i < n; ++i) {
if (i == 0 || t[i] != t[i - 1]) {
t[m++] = t[i];
}
}
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
ans[i] = Arrays.binarySearch(t, 0, m, arr[i]) + 1;
}
return ans;
}
}

• class Solution {
public:
vector<int> arrayRankTransform(vector<int>& arr) {
vector<int> t = arr;
sort(t.begin(), t.end());
t.erase(unique(t.begin(), t.end()), t.end());
vector<int> ans;
for (int x : arr) {
ans.push_back(upper_bound(t.begin(), t.end(), x) - t.begin());
}
return ans;
}
};

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


• func arrayRankTransform(arr []int) (ans []int) {
t := make([]int, len(arr))
copy(t, arr)
sort.Ints(t)
m := 0
for i, x := range t {
if i == 0 || x != t[i-1] {
t[m] = x
m++
}
}
t = t[:m]
for _, x := range arr {
ans = append(ans, sort.SearchInts(t, x)+1)
}
return
}

• function arrayRankTransform(arr: number[]): number[] {
const t = [...arr].sort((a, b) => a - b);
let m = 0;
for (let i = 0; i < t.length; ++i) {
if (i === 0 || t[i] !== t[i - 1]) {
t[m++] = t[i];
}
}
const search = (t: number[], right: number, x: number) => {
let left = 0;
while (left < right) {
const mid = (left + right) >> 1;
if (t[mid] > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
const ans: number[] = [];
for (const x of arr) {
ans.push(search(t, m, x));
}
return ans;
}