Rank Transform of an Array

Difficulty: Easy | Acceptance: 70.80% | Paid: No Topics: Array, Hash Table, Sorting

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
• Constraints
• Brute Force
• Sorting + Hash Map

Examples

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: All elements are equal, so they all have 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 <= 10^5
- -10^9 <= arr[i] <= 10^9

Brute Force

Intuition For each element in the array, we can determine its rank by counting how many unique elements in the array are smaller than it. The rank is then this count plus one.

Steps

• Initialize an empty result array.
• Iterate through each element x in the input array.
• For each x, iterate through the array again to count how many unique numbers are strictly smaller than x.
• Set the rank of x to be the count of smaller unique numbers + 1.
• Store the rank in the result array.
• Return the result array.

class Solution:
    def arrayRankTransform(self, arr: list[int]) -> list[int]:
        n = len(arr)
        res = [0] * n
        for i in range(n):
            unique_smaller = set()
            for j in range(n):
                if arr[j] < arr[i]:
                    unique_smaller.add(arr[j])
            res[i] = len(unique_smaller) + 1
        return res

Complexity

• Time: O(n²) - For each element, we traverse the array to find smaller unique elements.
• Space: O(n) - To store the result and the set of unique smaller elements.
• Notes: This approach is inefficient for large inputs (n up to 10⁵) and will result in Time Limit Exceeded.

Sorting + Hash Map

Intuition We can sort the array to easily determine the order of elements. By iterating through the sorted array, we can assign ranks to unique values sequentially. We then use a hash map to store the rank for each value, allowing us to transform the original array in linear time.

Steps

• Create a copy of the original array and sort it.
• Initialize an empty hash map and a rank counter starting at 1.
• Iterate through the sorted array. If the current element is not already in the hash map, assign it the current rank value, increment the rank, and store the mapping in the hash map.
• Iterate through the original array and replace each element with its corresponding rank found in the hash map.
• Return the modified array.

class Solution:
    def arrayRankTransform(self, arr: list[int]) -> list[int]:
        sorted_arr = sorted(arr)
        ranks = {}
        rank = 1
        for num in sorted_arr:
            if num not in ranks:
                ranks[num] = rank
                rank += 1
        return [ranks[num] for num in arr]

Complexity

• Time: O(n log n) - Dominated by the sorting step.
• Space: O(n) - To store the sorted array and the hash map.
• Notes: This is the optimal approach for this problem, handling duplicates and large input sizes efficiently.