Rank Transform of an Array

Problem Statement

In the given problem, we are provided with an array of integers named arr. Our task is to transform each element in the given array into its respective rank. The ranking of the array elements is determined by their sizes relative to each other, with a few specific rules:

1. Rankings are consecutive integers starting from 1.
2. A larger number implies a higher rank. However, if two numbers are identical, their ranks should be the same.
3. The ranks should be assigned in such a way that the smallest number receives the rank of 1, the next distinct greater number receives a rank of 2, and so on.

This transformation effectively sorts the array numbers in ascending order and then assigns ranks based on this sorted position while handling ties appropriately.

Examples

Example 1

Input:

arr = [40,10,20,30]

Output:

[4,1,2,3]

Explanation:

40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2

Input:

arr = [100,100,100]

Output:

[1,1,1]

Explanation:

Same elements share the same 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 <= 105
• -109 <= arr[i] <= 109

Approach and Intuition

Understanding the algorithm involves several intuitive steps crucial to tackle the problem effectively:

1. Sort the array: The first step involves sorting the array. This allows us to easily allocate ranks because, in a sorted list, every next element is greater than or equal to the previous.

2. Handle duplicates: While iterating through the sorted list, it's essential to check for duplicate values. Identical numbers should have the same rank, which adds a condition where we only increment our rank counter when we encounter a new number.

3. Mapping ranks: Once we have processed the ranks through the sorted list, we need to map these ranks back to the original array's structure. This involves creating a dictionary where keys are the original array's elements, and their values are the respective ranks.

4. Reconstruct the result: Utilize the constructed dictionary to transform the original array into a ranked array by replacing each element with its corresponding rank from the dictionary.

This methodology effectively uses sorting and mapping to achieve a time complexity primarily dominated by the sorting step, making it efficient given the constraints provided.

Solutions

class Solution {
public:
    vector<int> rankTransform(vector<int>& elements) {
        map<int, vector<int>> valueToPositions;
    
        for (int idx = 0; idx < elements.size(); idx++) {
            valueToPositions[elements[idx]].push_back(idx);
        }
    
        int currentRank = 1;
        for (auto& item : valueToPositions) {
            for (int pos : item.second) {
                elements[pos] = currentRank;
            }
            currentRank++;
        }
        return elements;
    }
};