Rank Transform of an Array

Leetcode Problem:

• Rank Transform of an Array

Summary

• Given an array of integers, replace each element with its rank
• The rank represents how large the element is.

Approach

• The approach used is to first sort the array and then create a map to store the rank of each unique number
• Then, for each number in the original array, find its rank in the map and add it to the result vector.

Complexity

• O(n log n) due to the sorting step, where n is the number of elements in the array.

Solution Code:

class Solution {
public:
    vector arrayRankTransform(vector& arr) {
        vector arr2 = arr;
        sort(arr2.begin(), arr2.end());
        unordered_map m;
        
        int rank = 0;
        int curNum = -1;
        for(int num : arr2){
            if(curNum == num){
                continue;
            }
            curNum = num;
            rank++;
            m[num] = rank;
        }

        vector ans;
        for(int num: arr){
            ans.push_back(m[num]);
        }
        return ans;
    }
};