Rank Transform of an Array
Problem
Given an array of integers arr, replace every element with its rank and return the result. Ranks start at 1: the smallest value gets rank 1, larger values get larger ranks, and equal values must always receive the same rank.
The recipe: sort a copy of the array, drop duplicates, record each distinct value's 1-based position in a hash map, then walk the original array swapping every value for its stored rank.
arr = [37,12,28,9,100,56,80,5,12][5,3,4,2,8,6,7,1,3]def array_rank_transform(arr):
sorted_unique = sorted(set(arr))
ranks = {}
for i, v in enumerate(sorted_unique):
ranks[v] = i + 1
return [ranks[v] for v in arr]function arrayRankTransform(arr) {
const sortedUnique = [...new Set(arr)].sort((a, b) => a - b);
const ranks = new Map();
sortedUnique.forEach((v, i) => ranks.set(v, i + 1));
return arr.map(v => ranks.get(v));
}int[] arrayRankTransform(int[] arr) {
int[] sorted = arr.clone();
Arrays.sort(sorted);
Map<Integer, Integer> ranks = new HashMap<>();
for (int v : sorted) {
ranks.putIfAbsent(v, ranks.size() + 1);
}
int[] ans = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
ans[i] = ranks.get(arr[i]);
}
return ans;
}vector<int> arrayRankTransform(vector<int>& arr) {
vector<int> sorted(arr);
sort(sorted.begin(), sorted.end());
unordered_map<int, int> ranks;
for (int v : sorted) {
int r = ranks.size() + 1;
if (!ranks.count(v)) ranks[v] = r;
}
vector<int> ans;
for (int v : arr) ans.push_back(ranks[v]);
return ans;
}Explanation
The key insight is that an element's rank depends on exactly one thing: how many distinct values are smaller than it. If three distinct values are smaller, its rank is 4 — no matter where it sits in the array and no matter how many copies of it exist. So we never need to compare elements pairwise; we only need each distinct value's position in sorted order.
That suggests a two-phase plan. Phase one: sort a deduplicated copy of the array. After sorting, the distinct value at index i has exactly i distinct values below it, so its rank is simply i + 1. We record this in a hash map ranks keyed by value. Phase two: walk the original array in its original order and replace each element v with ranks[v] — an O(1) lookup per element.
Deduplication is what makes equal values behave correctly. Because the map holds a single entry per value, every copy of 12 looks up the same entry and gets the same rank. Skipping it would break things: in [10, 10, 20] a non-deduplicated sorted copy would put 20 at index 2 and wrongly give it rank 3 instead of 2.
Walk through the default example arr = [37,12,28,9,100,56,80,5,12]. Sorting the distinct values gives [5, 9, 12, 28, 37, 56, 80, 100], so the map becomes 5→1, 9→2, 12→3, 28→4, 37→5, 56→6, 80→7, 100→8. Translating the original array element by element yields [5, 3, 4, 2, 8, 6, 7, 1, 3] — note both 12s map to rank 3.
The sort costs O(n log n) and dominates the running time; building the map and translating the array are each a single O(n) pass with O(1) hash operations. The map, the sorted copy, and the answer each hold at most n entries, so the extra space is O(n).