Rank Transform Of An Array - Leetcode Solution

Problem:

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1. The larger the element, the larger the rank. If two elements are equal, their rank must be the same. Rank should be as small as possible.

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

Solution:

To solve this problem, we can use two main approaches. One is to sort the input array and then calculate rank. The other approach is to use a hash table to calculate the rank.

Approach 1: Sort the input array and then calculate rank

In this approach, we will first sort the input array in increasing order. We will then assign rank to each element of the sorted array in increasing order. We will then create a hash table to store the rank of each element in the input array and return the rank of each element.

The algorithm is as follows:

1. Sort the input array in increasing order.
2. Initialize a hash table to store the rank of each element.
3. Iterate over the sorted array, and assign rank to each element based on its index in the sorted array.
4. Store the rank of each element in the hash table.
5. Iterate over the input array, retrieve rank from the hash table, and replace the element with its rank.
6. Return the updated input array.

Code:

The Python code for this approach is as follows:

def arrayRankTransform(self, arr: List[int]) -> List[int]: sorted_arr = sorted(set(arr)) rank = {num: i+1 for i, num in enumerate(sorted_arr)} return [rank[num] for num in arr]

Time Complexity:

The time complexity of this approach is O(n*log n), where n is the size of the input array. The log n factor come from sorting.

Space Complexity:

The space complexity of this approach is O(n), where n is the size of the input array. The space is needed to store the sorted array and hash table.

Approach 2: Use a hash table to calculate the rank

In this approach, we will use a hash table to calculate the rank of each element in the input array. We will iterate over the input array, and for each element, we will check if it is already in the hash table or not. If it is not present, we will add it to the hash table with a rank of the current size of the hash table. If it is present, we will ignore it. We will then replace each element of the input array with its rank in the hash table.

The algorithm is as follows:

1. Initialize a hash table to store the rank of each element.
2. Iterate over the input array.
3. If the current element is not present in the hash table, add it with a rank of the current size of the hash table.
4. Replace each element of the input array with its rank in the hash table.
5. Return the updated input array.

Code:

The Python code for this approach is as follows:

def arrayRankTransform(self, arr: List[int]) -> List[int]: rank = {} for num in sorted(arr): rank.setdefault(num, len(rank)+1) return [rank[num] for num in arr]

Time Complexity:

The time complexity of this approach is O(n*log n), where n is the size of the input array. The log n factor come from sorting.

Space Complexity:

The space complexity of this approach is O(n), since we are using a hash table to store the rank of each element.

1