Rank Transform of an Array

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

This C++ solution outlines a method to transform an array of integers into their corresponding rank form. The approach involves mapping each unique number to all its positions in the original array, sorting them, and then assigning ranks based on their sorted order. Follow this strategy to implement the rank transformation:

1. Initialize a map<int, vector<int>> to associate each unique integer with a list of its positions in the array.
2. Iterate through the array using a for-loop, populating the map with indices corresponding to each value.
3. Use a separate integer, starting at 1, to hold the current rank.
4. Loop through the map, which is inherently ordered by the integer keys (the unique values of the array). For each unique value (and its list of positions):
   • Update all occurrences of that value in the array to the current rank.
   • Increment the rank.
5. After completing the loop, return the modified array, which now contains the rank values instead of the original integers.

This method efficiently computes the rank transformation using the natural ordering provided by the C++ map, ensuring that the elements are ranked in ascending order of their values.

class Solution {

    public int[] transformArray(int[] inputArray) {
        // TreeMap will sort keys and store indices
        TreeMap<Integer, List<Integer>> valueToPosition = new TreeMap<>();

        for (int index = 0; index < inputArray.length; index++) {
            if (!valueToPosition.containsKey(inputArray[index])) {
                valueToPosition.put(inputArray[index], new ArrayList<>());
            }
            valueToPosition.get(inputArray[index]).add(index);
        }
        int currentRank = 1;
        for (int value : valueToPosition.keySet()) {
            for (int position : valueToPosition.get(value)) {
                inputArray[position] = currentRank;
            }
            currentRank++;
        }
        return inputArray;
    }
}

The Java solution provided outlines a method to rank transform an array. In rank transformation, each element in the original array is replaced by its ranking when the array is sorted.

The approach uses a TreeMap to manage the association between elements and their positions in the original array. A TreeMap automatically sorts keys, making it a suitable choice for this problem where sorting is essential. Here's a concise breakdown of the implementation:

1. Instantiate a TreeMap called valueToPosition where keys are the array elements, and values are lists holding the indices of these elements in the original array. This helps in dealing with duplicates.

2. Traverse the input array, adding entries to the TreeMap. If the current array value isn't already a key in the map, create a new entry with the value as the key. Add the current index to the corresponding list.

3. Initialize a rank counter currentRank starting from 1.

4. Loop through the sorted keys in the TreeMap. For each key (which corresponds to the unique values in the original array sorted in ascending order):

   • Access the list of positions for this value.
   • Replace the elements at each of these positions in the inputArray with the currentRank.
   • Increment currentRank for each unique value processed.

5. Finally, return the modified inputArray, which now holds the rank transformations.

This technique ensures that elements are transformed into their respective ranks based on ascending order, and elements with the same value receive the same rank.

class Solution:
    def rank_transform(self, nums: List[int]) -> List[int]:
        value_to_positions = {value: [] for value in sorted(set(nums))}

        for idx, value in enumerate(nums):
            value_to_positions[value].append(idx)

        current_rank = 1
        for value in value_to_positions.keys():
            for position in value_to_positions[value]:
                nums[position] = current_rank
            current_rank += 1

        return nums

The Python code provided offers a solution for transforming an array into its rank form. This method works as follows:

• A dictionary (value_to_positions) is initialized to store indices of each unique number in the sorted list of numbers.
• Loop through nums, assigning each number's indices to its respective place in value_to_positions.
• Initialize a variable current_rank to 1. For each unique number (accessed in ascending order), replace the numbers in nums at the indices stored in value_to_positions with current_rank.
• Increment current_rank after updating all positions of a particular number.
• Finally, the function returns nums where each element is replaced by its rank relative to the other elements in the input list.

This approach ensures that the elements of the original list are replaced by their ranks, which reflect the size relationship among elements (e.g., the smallest element gets rank 1, the next smallest gets rank 2, and so on). This is a space-efficient solution, making use of a dictionary for direct access operations, which generally provides a good balance between time complexity and readability.