Rank Transform of an Array — Solution in Python, Java & C++
Rank Transform of an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Rank Transform of an Array is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Replace each element of arr with its rank, where:
- ranks start at 1,
- a larger element has a larger rank,
- equal elements share the same rank,
- ranks are as small as possible.
Return the transformed array.
Example 1
Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Example 2
Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Equal elements share a 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 <= 100000-1000000000 <= arr[i] <= 1000000000
Hints for Rank Transform of an Array
Hint 1
Sort the distinct values to get the ranking order.
Hint 2
Map each distinct value to its 1-based position in that sorted list.
Hint 3
Then rewrite the original array through the map.
How to solve Rank Transform of an Array
Deduplicate, sort, and number. "Ranks as small as possible" means consecutive integers over the distinct values.
Approach
- Collect the distinct values and sort them ascending.
- Assign rank
i + 1to the value at indexi. - Map every element of the original array through that table.
Why it works
Sorting the distinct values puts them in rank order, and numbering them consecutively from 1 leaves no gaps — which is exactly the minimality requirement. Equal values share one map entry, so they share a rank automatically.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Sorting with duplicates and using the index gives gaps:
[100,100,100]would become[1,2,3]. - An empty array must produce an empty array.
- Ranks are 1-based, not 0-based.
Reference solution
Python
from typing import List
def arrayRankTransform(arr: List[int]) -> List[int]:
rank = {v: i + 1 for i, v in enumerate(sorted(set(arr)))}
return [rank[x] for x in arr]Java
public static int[] arrayRankTransform(int[] arr) {
int[] sorted = arr.clone();
Arrays.sort(sorted);
HashMap<Integer, Integer> rank = new HashMap<>();
int next = 1;
for (int v : sorted) {
if (!rank.containsKey(v)) rank.put(v, next++);
}
int[] out = new int[arr.length];
for (int i = 0; i < arr.length; i++) out[i] = rank.get(arr[i]);
return out;
}C++
vector<int> arrayRankTransform(vector<int>& arr) {
vector<int> sorted = arr;
sort(sorted.begin(), sorted.end());
unordered_map<int, int> rank;
int next = 1;
for (int v : sorted) {
if (rank.find(v) == rank.end()) rank[v] = next++;
}
vector<int> out;
for (int x : arr) out.push_back(rank[x]);
return out;
}JavaScript
var arrayRankTransform = function(arr) {
const seen = {};
const distinct = [];
for (let i = 0; i < arr.length; i++) {
const k = String(arr[i]);
if (seen[k] !== true) { seen[k] = true; distinct.push(arr[i]); }
}
distinct.sort(function(a, b) { return a - b; });
const rank = {};
for (let i = 0; i < distinct.length; i++) rank[String(distinct[i])] = i + 1;
const out = [];
for (let i = 0; i < arr.length; i++) out.push(rank[String(arr[i])]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets