Rank Transform of an Array

Easy
596.

Rank Transform of an Array

Rank Transform of an Array is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var arrayRankTransform = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Sort the distinct values to get the ranking order.

  2. Hint 2

    Map each distinct value to its 1-based position in that sorted list.

  3. 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

  1. Collect the distinct values and sort them ascending.
  2. Assign rank i + 1 to the value at index i.
  3. 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