Rank Transform of an Array solution and explanation
TCS
Google
9 more videos on this problem
Rank Transform of an Array | Leetcode 1331Techdose · 9:05 · 7K views
1331. Rank Transform of an Array | priority queue | treeset | Leetcode Daily Challenge | DSA | JavaShashCode · 22:45 · 4K views
1331. Rank Transform of an Array (LeetCode)hakunamatasq · 4:25 · 1K views
How to Solve "1331 Rank Transform of an Array" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 6:42 · 1K views
RANK TRANSFORM OF AN ARRAY | LEETCODE 1331 | PYTHON SOLUTIONCracking FAANG · 3:55 · 1K views
1331. Rank Transform of an Array | Leetcode Daily - PythonLeetcode Daily · 4:54 · 815 views
1331. Rank Transform of an Array | LeetCode Solution in Java | Step-by-Step Explanation | HindiCoding Sphere · 6:46 · 346 views
Daily Leetcode #2294: Jul 12, 2026 - 1331. Rank Transform of an ArrayProgramming Live with Larry · 2:53 · 334 views
Rank Transform of an Array - Leetcode 1331 - JavaCode With K5KC · 7:01 · 315 views
Leetcode 1331: Rank Transform of an Array | C++ | Leetcode Daily Challenge🔥Wingineers · 7:32 · 255 views
The problem
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
Approach overview
Problem Overview: Given an integer array, replace every element with its rank after sorting the values in ascending order. The smallest value gets rank 1. Equal values share the same rank, and ranks increase only when the value changes.
Approach 1: Sorting and Ranking (O(n log n) time, O(n) space)
This approach sorts the unique values and assigns ranks incrementally. Start by copying the array and sorting it. Then iterate through the sorted list and build a hash table that maps each number to its rank. Only assign a new rank when the current value differs from the previous value so duplicates receive the same rank. Finally, iterate through the original array and replace each value with its stored rank using constant-time hash lookups.
The key insight is separating ordering from mapping. Sorting determines the rank order, while the hash map allows quick translation back to the original positions. This approach works well for most cases and keeps the implementation simple. Time complexity comes from sorting the array (O(n log n)) and the additional passes are linear.
Approach 2: Using Coordinate Compression (O(n log n) time, O(n) space)
Coordinate compression reduces large or scattered values into a compact rank range. First, copy the array and sort it. Remove duplicates from the sorted list so you only keep unique values. Each unique value’s index in this sorted list determines its rank (index + 1). Store these mappings in a dictionary and then transform the original array by replacing each element with its compressed coordinate (rank).
This method is conceptually similar to the first approach but emphasizes the compression idea commonly used in competitive programming and sorting problems. It is especially useful when the input values are very large or sparse but you only care about relative ordering. By compressing them into ranks, you reduce the value domain without losing ordering information.
Both methods rely on sorting to establish global ordering and use a array traversal to rebuild the result. The difference is mainly conceptual: the first focuses on ranking while the second frames the process as coordinate compression.
Recommended for interviews: The sorting + hash map solution is the most direct and the one interviewers typically expect. It clearly demonstrates understanding of ordering, duplicate handling, and efficient lookups. Mentioning coordinate compression shows deeper algorithmic awareness, especially in problems involving large ranges or index remapping.
Approach 1: Sorting and Ranking
This approach involves sorting the array to determine the rank of each element. After sorting, unique elements are mapped to their ranks.
def arrayRankTransform(arr):
sorted_arr = sorted(arr)
rank_map = {}
rank = 1
for num in sorted_arr:
if num not in rank_map:
rank_map[num] = rank
rank += 1
return [rank_map[num] for num in arr]import java.util.*;
class Solution {
public int[] arrayRankTransform(int[] arr) {
int[] sorted = arr.clone();
Arrays.sort(sorted);
Map<Integer, Integer> rankMap = new HashMap<>();
int rank = 1;
for (int num : sorted) {
if (!rankMap.containsKey(num)) {
rankMap.put(num, rank++);
}
}
for (int i = 0; i < arr.length; i++) {
arr[i] = rankMap.get(arr[i]);
}
return arr;
}
}#include <vector>
#include <map>
#include <algorithm>
using namespace std;
vector<int> arrayRankTransform(vector<int>& arr) {
vector<int> sorted = arr;
sort(sorted.begin(), sorted.end());
map<int, int> rankMap;
int rank = 1;
for (int num : sorted) {
if (rankMap.find(num) == rankMap.end()) {
rankMap[num] = rank++;
}
}
vector<int> result;
for (int num : arr) {
result.push_back(rankMap[num]);
}
return result;
}var arrayRankTransform = function(arr) {
const sorted = [...arr].sort((a, b) => a - b);
const rankMap = new Map();
let rank = 1;
for (let num of sorted) {
if (!rankMap.has(num)) {
rankMap.set(num, rank++);
}
}
return arr.map(num => rankMap.get(num));
};#include <stdio.h>
#include <stdlib.h>
int cmpfunc (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
int* arrayRankTransform(int* arr, int arrSize, int* returnSize) {
*returnSize = arrSize;
if (arrSize == 0) return NULL;
int* sorted = (int*)malloc(arrSize * sizeof(int));
for (int i = 0; i < arrSize; i++) sorted[i] = arr[i];
qsort(sorted, arrSize, sizeof(int), cmpfunc);
int* rankMap = (int*)malloc(arrSize * sizeof(int));
int rank = 1;
rankMap[0] = sorted[0];
int rankArr[1] = {rank};
for (int i = 1; i < arrSize; i++) {
if (sorted[i] != sorted[i - 1]) {
rank++;
}
rankArr[rank] = sorted[i];
}
int* result = (int*)malloc(arrSize * sizeof(int));
for (int i = 0; i < arrSize; i++) {
for (int j = 0; j < rank; j++) {
if (arr[i] == rankMap[j]) {
result[i] = j + 1;
break;
}
}
}
free(sorted);
free(rankMap);
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] ArrayRankTransform(int[] arr) {
int[] sorted = (int[])arr.Clone();
Array.Sort(sorted);
Dictionary<int, int> rankMap = new Dictionary<int, int>();
int rank = 1;
foreach (int num in sorted) {
if (!rankMap.ContainsKey(num)) {
rankMap[num] = rank++;
}
}
for (int i = 0; i < arr.Length; i++) {
arr[i] = rankMap[arr[i]];
}
return arr;
}
}This Python solution sorts the array to determine the ranks and uses a dictionary to map each unique element to its rank. Finally, it generates the ranked array using this mapping.
Time Complexity: O(N log N) due to sorting.
Space Complexity: O(N) for the rank dictionary.
Approach 2: Using Coordinate Compression
Coordinate compression is a method to map large ranges of numbers to smaller ranges, maintaining their relative order. This approach uses this idea to assign ranks.
def arrayRankTransform(arr):
sorted_arr = sorted(arr)
rank_map = {}
rank = 1
for num in sorted_arr:
if num not in rank_map:
rank_map[num] = rank
rank += 1
return [rank_map[num] for num in arr]#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<int> arrayRankTransform(vector<int>& arr) {
vector<int> sorted = arr;
sort(sorted.begin(), sorted.end());
unordered_map<int, int> rankMap;
int rank = 1;
for (int num : sorted) {
if (!rankMap.count(num)) {
rankMap[num] = rank++;
}
}
vector<int> result(arr.size());
transform(arr.begin(), arr.end(), result.begin(), [&rankMap](int num) { return rankMap[num]; });
return result;
}#include <stdio.h>
#include <stdlib.h>
int cmpfunc (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
int* arrayRankTransform(int* arr, int arrSize, int* returnSize) {
*returnSize = arrSize;
if (arrSize == 0) return NULL;
int* sorted = (int*)malloc(arrSize * sizeof(int));
for (int i = 0; i < arrSize; i++) sorted[i] = arr[i];
qsort(sorted, arrSize, sizeof(int), cmpfunc);
int* rankMap = (int*)malloc(arrSize * sizeof(int));
int* result = (int*)malloc(arrSize * sizeof(int));
int rank = 1;
for (int i = 0; i < arrSize; i++) {
if (i == 0 || sorted[i] != sorted[i - 1]) {
rankMap[i] = rank++;
} else {
rankMap[i] = rankMap[i - 1];
}
}
for (int i = 0; i < arrSize; i++) {
int index = (int)(bsearch(&arr[i], sorted, arrSize, sizeof(int), cmpfunc) - sorted);
result[i] = rankMap[index];
}
free(sorted);
free(rankMap);
return result;
}Coordinate compression in this Python solution involves using sorting and a dictionary for mapping ranks. The sorted elements guide the rank allocation to the array with minimal memory use.
Time Complexity: O(N log N) due to sorting.
Space Complexity: O(N) for storing ranks in the dictionary.
Approach 3: Discretization
First, we copy an array t, then sort and deduplicate it to obtain an array of length m that is strictly monotonically increasing.
Next, we traverse the original array arr. For each element x in the array, we use binary search to find the position of x in t. The position plus one is the rank of x.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array arr.
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;
}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
}Approach 4: Sorting + Hash Map
function arrayRankTransform(arr: number[]): number[] {
const sorted = [...new Set(arr)].sort((a, b) => a - b);
const map = new Map<number, number>();
let c = 1;
for (const x of sorted) {
map.set(x, c++);
}
return arr.map(x => map.get(x)!);
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Ranking | Time Complexity: O(N log N) due to sorting. |
| Using Coordinate Compression | Time Complexity: O(N log N) due to sorting. |
| Discretization | – |
| Sorting + Hash Map | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Ranking with Hash Map | O(n log n) | O(n) | General case. Clear implementation and easy to explain during interviews. |
| Coordinate Compression | O(n log n) | O(n) | Useful when values are large or sparse and you want to remap them into a compact rank range. |
Frequently asked questions
Is Rank Transform of an Array easy or hard?
Rank Transform of an Array is categorized as an Easy problem on LeetCode with a high acceptance rate around 70%. The challenge mainly involves handling duplicates correctly while assigning ranks after sorting. Understanding hash maps and sorting is sufficient to solve it.
How to solve Rank Transform of an Array in O(n)?
A true O(n) solution is generally not possible because the algorithm needs global ordering of elements, which requires sorting. Without constraints on the value range, comparison-based sorting leads to O(n log n) time. If the value range were very small, counting sort could theoretically reduce the complexity closer to O(n).
Rank Transform of an Array Python or Java solution?
In Python or Java, the standard solution sorts a copy of the array, builds a dictionary or HashMap mapping values to ranks, and then replaces each original value with its rank. The approach works the same across languages and maintains O(n log n) time complexity.
What is the best approach for Rank Transform of an Array?
The most common solution sorts the array values and assigns ranks using a hash map. After sorting, each unique number receives an increasing rank, and duplicates share the same rank. The original array is then transformed using constant-time lookups. This approach runs in O(n log n) time and O(n) space.
What data structure is used in Rank Transform of an Array?
The typical implementation uses a hash table to map each value to its rank after sorting. Arrays are used for iteration and reconstruction of the final result. Sorting algorithms provide the ordering needed to assign correct ranks.
What is the time complexity of Rank Transform of an Array?
The optimal solution runs in O(n log n) time due to the sorting step. After sorting, assigning ranks and reconstructing the result both take O(n). Space complexity is O(n) because a hash map or auxiliary array is used to store value-to-rank mappings.
Is Rank Transform of an Array asked at Google, Amazon, or Meta?
Variants of ranking and coordinate compression problems appear in interviews at companies like Amazon and Google. The question tests understanding of sorting, handling duplicates, and mapping values efficiently using hash tables. It is commonly used as an easy-to-medium warm-up problem.