Code Logo

Rank Transform of an Array

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given an array of integers arr, replace each element with its rank. The rank is a 1-indexed integer representing the position of the element when the array is sorted in ascending order. Equal values share the same rank. For example, the smallest element gets rank 1, the next smallest gets rank 2, and so on.

The solution sorts a copy of the array with duplicates removed, then assigns ranks to unique values. A hash map stores the rank of each unique value. Finally, iterate through the original array and replace each element with its rank from the map.

This uses sorting for ordering and a hash map for O(1) lookup during the replacement pass. The time is O(n log n) for sorting plus O(n) for the passes. Memory is O(n) for the hash map and sorted array.

Edge cases include an empty array (return []), a single element (return [1]), all elements equal (return array of 1s), and negative values.

The rank transform combines sorting with hash map lookups: sort unique values, assign ranks in order, then map each original element to its rank via the hash map. This two-phase approach (build mapping, then apply) is a common pattern in array transformation problems.

The rank transform has applications in data normalization and competitive ranking where absolute values are replaced with relative ordering positions.

Example Input & Output

Example 1
Input
[1]
Output
[1]
Explanation

Single element.

Example 2
Input
[40,10,20,30]
Output
[4,1,2,3]
Explanation

40->4, 10->1, 20->2, 30->3.

Example 3
Input
[100,100,100]
Output
[1,1,1]
Explanation

Same rank for equal values.

Example 4
Input
[]
Output
[]
Explanation

Empty.

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

12 appears twice, both rank 3.

Algorithm Flow

Recommendation Algorithm Flow for Rank Transform of an Array
Recommendation Algorithm Flow for Rank Transform of an Array

Solution Approach

Sort unique values. Assign ranks in a hash map. Replace each element with its rank.

function solution(arr) {
  var sorted = arr.slice().sort(function(a,b){return a-b;});
  var rank = {};
  var r = 1;
  for (var i = 0; i < sorted.length; i++) {
    if (!rank[sorted[i]]) rank[sorted[i]] = r++;
  }
  var result = [];
  for (var i = 0; i < arr.length; i++) {
    result.push(rank[arr[i]]);
  }
  return result;
}

Time O(n log n), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int[] solution(int[] arr) {
        int[] sorted=arr.clone();
        Arrays.sort(sorted);
        Map<Integer,Integer> rank=new HashMap<>();
        int r=1;
        for (int v:sorted) {
            if (!rank.containsKey(v)) rank.put(v,r++);
        }
        int[] res=new int[arr.length];
        for (int i=0;i<arr.length;i++) res[i]=rank.get(arr[i]);
        return res;
    }
}