LeetCode – Rank Transform of an Array

Link: https://leetcode.com/problems/rank-transform-of-an-array/

Solution 1 (Slower):

• removing duplicates
• sorting the array ascending
• map the initial array by finding the index of the element in the sorted list and add a + 1 to start the rank from 1

var arrayRankTransform = function(arr) {
    let unique = [...new Set(arr)];
    let sorted = unique.sort((a,b) => a-b);
    
    return arr.map(element => sorted.indexOf(element) + 1);
};

Complexity: O(n²)

---

Solution 2 (Faster):

• remove duplicates
• sort the array
• use a map to store the index of each element
• map the initial array by using the index from the map and add a + 1 to start the rank from 1

var arrayRankTransform = function(arr) {
    let unique = [...new Set(arr)];
    let sorted = unique.sort((a,b) => a-b);
    var map = {};
    
    for(var index = 0; index < arr.length; index++)
        map[sorted[index]] = index;

    return arr.map(element => map[element] + 1);
};

Complexity: Complexity: O(n)