Code Logo

Rank Transform of an Array

Published at24 Jul 2026
Created by
Easy 1 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

Solution Approach

Replace each element in an array with its rank (1-indexed position in sorted order). Create a sorted copy of the array with unique values and map each value to its rank. Then replace each element in the original array with its rank.

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

Duplicate values receive the same rank. Sorting and mapping in one pass assigns ranks sequentially, skipping duplicates.

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;
    }
}