Rank Transform Of An Array

Rank Transform of an Array is a sorting plus hash map problem. The rank of a value depends on its order among the distinct values, not on its original index.

Problem

Given an integer array arr, replace each value with its rank.

Rules:

the smallest value has rank 1
equal values get the same rank
ranks increase by 1 only when a new distinct value appears

Example:

arr = [40, 10, 20, 30]
result = [4, 1, 2, 3]

First Attempt

public int[] arrayRankTransform(int[] arr) {
    int[] sorted = arr.clone();
    Arrays.sort(sorted);

    Map<Integer, Integer> map = new HashMap();
    int n = arr.length;
    int rank = 1;

    for (int i = 0; i < n; i++) {
        if (!map.containsKey(sorted[i])) {
            map.put(sorted[i], rank);
            rank++;
        }
    }

    int[] ranked = new int[n];
    for (int i = 0; i < n; i++) {
        ranked[i] = map.get(arr[i]);
    }

    return ranked;
}

This is the right idea:

copy the array
sort the copy
assign ranks to distinct values
rebuild the answer using the original order

The key detail is using containsKey. Without that check, duplicate values would incorrectly increase the rank.

Clean Version

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int[] sorted = arr.clone();
        Arrays.sort(sorted);

        Map<Integer, Integer> rankByValue = new HashMap<>();
        int nextRank = 1;

        for (int value : sorted) {
            if (!rankByValue.containsKey(value)) {
                rankByValue.put(value, nextRank);
                nextRank++;
            }
        }

        int[] result = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            result[i] = rankByValue.get(arr[i]);
        }

        return result;
    }
}

The cleaned version keeps the same logic, but makes the variable names explain the job:

rankByValue: maps each distinct number to its rank
nextRank: the rank to assign to the next new value
result: the transformed array in the original order

Walkthrough

Input:

arr = [37, 12, 28, 9, 100, 56, 80, 5, 12]

Sorted copy:

[5, 9, 12, 12, 28, 37, 56, 80, 100]

Rank map:

value	rank
5	1
9	2
12	3
28	4
37	5
56	6
80	7
100	8

Now transform the original array:

[37, 12, 28, 9, 100, 56, 80, 5, 12]
[5,   3,  4, 2, 8,   6,  7,  1, 3]

Duplicate 12 appears twice, and both positions receive rank 3.

Edge Cases

[] -> []
[100] -> [1]
[100, 100, 100] -> [1, 1, 1]
[40, 10, 20, 30] -> [4, 1, 2, 3]

The empty array works naturally because both loops run zero times.

Complexity

Step	Time	Space
Clone and sort	`O(n log n)`	`O(n)`
Build rank map	`O(n)`	`O(n)`
Build result	`O(n)`	`O(n)`

Overall:

Time: O(n log n)
Space: O(n)

Takeaways

Sort a copy when the answer must preserve original order.
Use a map from value to rank so duplicates share the same rank.
Only increase the rank when a new distinct value appears.
This pattern is useful whenever sorted order defines labels, buckets, or priorities.