Leetcode 1331. Rank Transform of an Array

Problem

The problem is to rearrange the values in an integer array based on their rank. The rank is determined by the rules that (1) rank starts from 1, (2) the larger the element, the larger the rank, and if two elements are the same, their rank should also be the same, and (3) rank should be given the smallest possible value. For example, if the input array is [40,10,20,30], the output should be [4,1,2,3] because 40 is the largest element, 10 is the smallest, 20 is the second smallest, and 30 is the third smallest.

This problem uses the concept of hashing and sorting. The key idea of the solution is to calculate the rank of each number by sorting the array and storing each element and its rank in a dictionary. Then, replace each element in the original array with its rank from the dictionary.

Next, let's take a look at the solution step by step.

Example

Input array: [37,12,28,9,100,56,80,5,12]

First, sort the array in ascending order: [5,9,12,12,28,37,56,80,100]

Next, we create a dictionary and start assigning ranks:

{5:1, 9:2, 12:3, 28:4, 37:5, 56:6, 80:7, 100:8}

After that, we replace each element in the original array with its rank from the dictionary according to their values.

So, the output array will be: [5,3,4,2,8,6,7,1,3]

Python Solution

1
2python
3class Solution:
4    def arrayRankTransform(self, arr):
5        sorted_arr = sorted(set(arr)) # 1. Sort and remove duplicates
6        rank_dict = {num: i + 1 for i, num in enumerate(sorted_arr)} # 2. Assign ranks
7        return [rank_dict[num] for num in arr] # 3. Replace with rank

Java Solution

1
2java
3class Solution {
4    public int[] arrayRankTransform(int[] arr) {
5        int[] sortedArr = arr.clone(); // Create a copy of the array
6        Arrays.sort(sortedArr); // Sort the copy
7        Map<Integer, Integer> rankMap = new HashMap<>(); // Create map
8        for (int num : sortedArr) rankMap.putIfAbsent(num, rankMap.size() + 1); // Assign ranks
9        for (int i = 0; i < arr.length; i++) arr[i] = rankMap.get(arr[i]); // Replace with rank
10        return arr;
11    }
12}

C++ Solution

1
2cplusplus
3class Solution {
4public:
5    vector<int> arrayRankTransform(vector<int>& arr) {
6        vector<int> sortedArr = arr; // create a copy
7        sort(sortedArr.begin(), sortedArr.end()); // sort the copy
8        unordered_map<int, int> rankMap; // create map
9        for (auto &num : sortedArr) if (rankMap.find(num) == rankMap.end()) rankMap[num] = rankMap.size() + 1; // assign ranks
10        for (auto &num : arr) num = rankMap[num]; // replace with rank
11        return arr;
12    }
13};

JavaScript Solution

1
2javascript
3var arrayRankTransform = function(arr) {
4    let sortedArr = Array.from(new Set(arr)).sort((a,b) => a-b); // Sort and remove duplicates
5    let rankMap = new Map(sortedArr.map((value, index) => [value, index + 1])); // Assign ranks
6    return arr.map((value) => rankMap.get(value)); // Replace with rank
7};

C# Solution

1
2csharp
3public class Solution {
4    public int[] ArrayRankTransform(int[] arr) {
5        int[] sortedArr = (int[]) arr.Clone(); // create a copy
6        Array.Sort(sortedArr); // sort the copy
7        var rankDict = new Dictionary<int, int>(); // create map
8        foreach (int num in sortedArr) if (!rankDict.ContainsKey(num)) rankDict[num] = rankDict.Count + 1; // assign ranks
9        for (int i = 0; i < arr.Length; i++) arr[i] = rankDict[arr[i]]; // replace with rank
10        return arr;
11    }
12}

Each of the above solutions uses a data structure (Python's dictionary, Java and C#'s HashMap, C++'s unordered_map, JavaScript's Map) to store the ranks of each unique elements. In each solution, the array is cloned so that the original order can be preserved. Then the copy is sorted, and ranks for each unique element is saved in the combinatorial data structure(num -> rank). After that, each value in the original array is replaced with its rank to obtain the return result.## Ruby Solution

1
2ruby
3def arrayRankTransform(arr)
4    sorted_arr = arr.sort.uniq
5    rank_map = Hash.new
6    sorted_arr.each_with_index do |num, index|
7        rank_map[num] = index + 1
8    end
9    arr.map { |num| rank_map[num] }
10end

PHP Solution

1
2php
3class Solution {
4
5    function arrayRankTransform($arr) {
6        $sorted_arr = $arr;
7        sort($sorted_arr);
8        $rankMap = [];
9        foreach($sorted_arr as $num){
10            if( ! isset($rankMap[$num]) ){
11                $rankMap[$num] = sizeof($rankMap) + 1;
12            }
13        }
14        for($i=0;$i < sizeof($arr);$i++){
15            $arr[$i] = $rankMap[$arr[$i]];
16        }
17        return $arr;
18    }
19}

Although the approach and methods used to solve this problem are basically the same in different languages, the differences in the use of function names, grammars and data structures may cause the codes to appear very different. For instance, JavaScript, C#, and Python use a dictionary, C++ uses an unordered map, and PHP uses an associative array to implement the same logic.

Understanding the syntax and language-specific conventions makes it easier to translate the solution between different programming languages. Even though the languages vary, the problem-solving logic and step-by-step method are universally applicable to any languages that support basic data structures and algorithms.

This problem shows us a common strategy applied in many interview problems - using a hash table to store the relationship between original data and target data for efficient lookups. We also leverage the built-in sorting functions to determine the rank of each unique number. It's a great example of combining different algorithms and data structures to form a comprehensive solution.

Knowing these common techniques and being able to adapt them to different programming languages is an important skill for a software engineer or a full-stack developer. This ability will undoubtedly open up more opportunities and make you more versatile in your career as a software developer.