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.

Examples

Example 1:

1
2
3

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:

1
2
3

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

1
2

Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Solution

Method 1 - Sorting and Hashmap

Here is the approach:

  1. Sorting and Ranking:
    • First, we sort the array while keeping track of the original indices.
    • Use a dictionary to map each unique element to its rank.
    • Replace each element in the original array with its corresponding rank from the dictionary.
  2. Implementation Steps:
    • Create a sorted version of the array with original indices for easy lookup.
    • Create a dictionary to store the rank for each unique element.
    • Iterate over the original array, replacing each element with its rank from the dictionary.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Solution {
    public int[] arrayRankTransform(int[] arr) {
        if (arr.length == 0) {
            return arr;
        }
		//Make a copy of array so that we don't loose order of elements in original array
        int[] sortedArr = Arrays.copyOf(arr, arr.length);
        // sort the array
        Arrays.sort(sortedArr);

        Map<Integer, Integer> rankMap = new HashMap<>();
        int rank = 1;

        for (int i = 0; i < sortedArr.length; i++) {
	        // if map don't contain that element then map it with it's rank
            if (!rankMap.containsKey(sortedArr[i])) {
                rankMap.put(sortedArr[i], rank);
                rank++;
            }
            // otherwise that element rank is already calculated
        }

		// create the result array
        int[] res = new int[arr.length];
        // Put the ranks from the map into array
        for (int i = 0; i < arr.length; i++) {
            res[i] = rankMap.get(arr[i]);
        }

        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        if not arr:
            return arr

        # Step 1: Sort the array while keeping track of the original indices
        sorted_arr = sorted(enumerate(arr), key=lambda x: x[1])

        # Step 2: Create a rank dictionary
        rank_dict = {}
        rank = 1

        for i, (index, value) in enumerate(sorted_arr):
            if value not in rank_dict:
                rank_dict[value] = rank
                rank += 1

        # Step 3: Replace elements in original array with their corresponding rank
        result = [rank_dict[arr[i]] for i in range(len(arr))]
        return result

Complexity

  • ⏰ Time complexity: O(n log n), where n is number of elements in array
    • Sorting the array takes O(n log n).
    • Creating the rank dictionary and replacing elements takes O(n).
  • 🧺 Space complexity: O(n), to store the sorted array and the rank dictionary.