Code Implementation

class Solution:
    def arrayRankTransform(self, arr):
        # Remove duplicates and sort to get the order
        sorted_unique = sorted(set(arr))
        # Map each value to its rank (starting from 1)
        rank = {num: i+1 for i, num in enumerate(sorted_unique)}
        # Replace each element with its rank
        return [rank[num] for num in arr]
      

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        vector<int> sorted = arr;
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        unordered_map<int, int> rank;
        for (int i = 0; i < sorted.size(); ++i) {
            rank[sorted[i]] = i + 1;
        }
        vector<int> result;
        for (int num : arr) {
            result.push_back(rank[num]);
        }
        return result;
    }
};
      

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int[] sorted = arr.clone();
        Arrays.sort(sorted);
        Map<Integer, Integer> rank = new HashMap<>();
        int r = 1;
        for (int num : sorted) {
            if (!rank.containsKey(num)) {
                rank.put(num, r++);
            }
        }
        int[] result = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            result[i] = rank.get(arr[i]);
        }
        return result;
    }
}
      

var arrayRankTransform = function(arr) {
    // Copy and sort unique values
    let sorted = Array.from(new Set(arr)).sort((a, b) => a - b);
    // Map original value to its rank
    let rank = new Map();
    for (let i = 0; i < sorted.length; i++) {
        rank.set(sorted[i], i + 1);
    }
    // Build result
    return arr.map(num => rank.get(num));
};
      

Problem Description

Given an integer array arr, you are asked to transform the array so that each element is replaced by its "rank". The rank of an element is its position in the sorted list of unique values from arr (with the smallest element having rank 1, the next smallest rank 2, and so on). If two elements are equal, they receive the same rank. The ranking must be stable and consecutive without gaps.

Constraints:

• All elements in arr are integers (can be negative, zero, or positive).
• The output array must have the same length as arr.
• Ranks start from 1 and are assigned in order of increasing value.
• Equal elements must have the same rank.

Thought Process

At first, one might think of comparing each element to every other element to determine its rank, but this would be inefficient. The core idea is to assign ranks based on the sorted order of unique values. If we sort the array and remove duplicates, we can easily assign increasing ranks. Then, by mapping each original value to its rank, we can efficiently transform the original array.

The main challenge is to handle duplicate values correctly (assigning the same rank) and to ensure ranks are assigned consecutively starting from 1. Using a mapping (like a hash map or dictionary) allows us to look up ranks quickly for each element in the original array.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Extract Unique Values:
   • We want to assign ranks based on unique values, so we start by removing duplicates from arr.
2. Sort Unique Values:
   • Sorting gives us the order in which ranks should be assigned (smallest to largest).
3. Assign Ranks:
   • We iterate through the sorted unique values, assigning consecutive ranks (starting from 1).
   • We store these mappings in a hash map or dictionary for fast lookup.
4. Transform the Original Array:
   • We replace each element in the original array with its corresponding rank using our mapping.

We use a hash map (or dictionary) for O(1) rank lookups, and sorting ensures the correct rank order. This approach is much faster and cleaner than comparing each element to every other element.

Example Walkthrough

Let's use the input arr = [40, 10, 20, 30, 20, 10] as an example.

1. Extract Unique Values:
   • Unique values: [10, 20, 30, 40]
2. Sort Unique Values:
   • Already sorted: [10, 20, 30, 40]
3. Assign Ranks:
   • 10 → 1
   • 20 → 2
   • 30 → 3
   • 40 → 4
4. Transform the Original Array:
   • arr[0] = 40 → 4
   • arr[1] = 10 → 1
   • arr[2] = 20 → 2
   • arr[3] = 30 → 3
   • arr[4] = 20 → 2
   • arr[5] = 10 → 1

   Final Result: [4, 1, 2, 3, 2, 1]

Each original value is replaced by its rank, and duplicates share the same rank.

Time and Space Complexity

Brute-force Approach:

• If we compared every element to every other element to count how many are smaller, time complexity would be O(N^2), which is inefficient for large arrays.

• Extracting unique values: O(N) time and space (using a set/dictionary).
• Sorting unique values: O(M log M), where M is the number of unique elements (M ≤ N).
• Mapping values to ranks: O(M).
• Transforming the original array: O(N).
• Total Time Complexity: O(N log N) (since M ≤ N, sorting dominates).
• Space Complexity: O(N) for the mapping and result array.

This makes the optimized approach much more efficient and scalable.

Summary

The Rank Transform of an Array problem asks us to replace each element with its rank among unique, sorted values. The key insight is to use a combination of sorting and mapping to assign ranks efficiently, ensuring duplicates get the same rank. By leveraging data structures like sets and hash maps, we avoid unnecessary comparisons and achieve a clean, efficient O(N log N) solution. This approach is both elegant and practical for large inputs.