1331. Rank Transform of an Array

Problem Description

The problem states that we have an array of integers called arr. We need to transform this array so that instead of the original numbers, each element is replaced by its "rank". The rank of an element in the array is determined by the following rules:

• Rank is assigned starting from 1.
• The bigger the number, the higher the rank it should have.
• If two numbers are the same, they should have the same rank.
• The rank should be as small as possible, meaning that the smallest number gets rank 1, the second smallest gets rank 2, and so on, without any gaps in the ranks.

Therefore, the task is to rewrite the array in such a way that the numbers are replaced with their corresponding ranks.

Intuition

To come up with a solution to this problem, we can use a step-by-step approach. The first part of the problem suggests a sorting operation since we need to determine the order of the elements (to assign ranks properly). However, we must also handle duplicates (elements of equal value should have the same rank). To do this effectively, we can utilize the set data structure in Python, which stores only unique elements. Here is the intuition broken down:

• First, sort the unique elements of the array. This can be done by converting the array to a set to remove duplicates, and then converting it back to a list to sort it. This gives us a sorted list of the unique elements in ascending order.
• Second, to find the rank of the original elements, we need to determine their position in this sorted list of unique elements.
• Third, we use the bisect_right function from the bisect module in Python, which is designed to find the position in a sorted list where an element should be inserted to maintain sorted order. However, in our case, it effectively gives us the number of elements that are less than or equal to our target number. Since our list is already sorted, this is equivalent to finding the rank.
• Finally, apply the bisect_right operation to each element in the original array to replace it with its rank.

The elegance of this solution lies in its simplicity and efficiency. By using sorting and binary search (which bisect_right employs), we arrive at a solution that is both clear and optimized for performance.

Learn more about Sorting patterns.

Solution Approach

The implementation of the solution can be understood by breaking down the steps and the algorithms or data structures used in each.

The code begins by defining a method arrayRankTransform within the Solution class which takes one argument, the array arr.

The first line within the method:

1t = sorted(set(arr))

involves two operations:

• set(arr): Converts the list arr into a set, removing any duplicate elements.
• sorted(...): Takes the set of unique elements and returns a sorted list of these elements, t.

Now that t holds a sorted list of unique elements from the original array, the next step is to find out the rank of each element in the original array arr according to its position in t.

The following line:

1return [bisect_right(t, x) for x in arr]

uses a list comprehension to create a new list by going through each element x in the original array arr.

• For each element x, bisect_right(t, x) is called, which uses a binary search to find the insertion point for x in t to the right of any existing entries. Essentially, it finds the index of the first element in the sorted list t that is greater than x.

Since t is sorted and contains every unique value from arr, the index returned by bisect_right corresponds to the number of elements less than or equal to x. This is exactly the rank of x because:

• The smallest element in arr will have a rank of 1 (because there will be 0 elements smaller than it in t).
• If elements in arr are equal, they will have the same rank since bisect_right will return the same index for them.
• Every unique element will have a unique rank in increasing order.

By combining set, sorted, and bisect_right, the solution effectively creates a ranking system for the elements in the array arr. It does so without the need for cumbersome loops or manually implementing a binary search, instead relying on Python's built-in high-performance algorithms.

Finally, the method returns the array which consists of ranks corresponding to each element in arr. This list represents the transformed version of the input where each value is replaced by its rank, effectively solving the problem.

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the following array:

1arr = [40, 20, 10, 10]

Following the solution approach step by step, we first convert the arr into a set to remove duplicates, and then sort it:

1. Convert to set:

   1{10, 20, 40}

   This set does not include duplicates and now contains only the unique values 10, 20, and 40.

2. Sort the unique elements:

   1t = [10, 20, 40]

   Now we have a sorted list t with the unique elements from the array in ascending order.

The next step is to find the rank for each element in arr by determining its position in the sorted list t using the binary search provided by the bisect_right function:

• For the first element 40 in arr, bisect_right(t, 40) returns 3 because there are two elements in t that are less than or equal to 40. Hence, its rank is 3.
• For the element 20 in arr, bisect_right(t, 20) returns 2, as there is only one element less than or equal to 20. Hence, its rank is 2.
• For the first 10 in arr, bisect_right(t, 10) returns 1, since there are no elements in t that are less than 10. Hence, its rank is 1.
• The second 10 in arr will have the same rank as the first 10 since they are equal. Therefore, bispect_right(t, 10) again returns 1.

When we replace each element in arr with its calculated rank, we get the final transformed array:

1arr = [3, 2, 1, 1]

Each number in the original array has now been replaced with its respective rank, completing the process. The code executing the described steps for the provided example would look like this:

1from bisect import bisect_right
2
3def arrayRankTransform(arr):
4    t = sorted(set(arr))
5    return [bisect_right(t, x) for x in arr]
6
7# Example array
8arr = [40, 20, 10, 10]
9
10# Transforming the array
11ranked_arr = arrayRankTransform(arr)
12# ranked_arr is now [3, 2, 1, 1]

This demonstrates how the algorithm effectively translates the initial array into one representing the ranks of each element.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code can be broken down into the following parts:

1. sorted(set(arr)): Creating a set from the array removes duplicates and takes O(n) time, where n is the number of elements in arr. Sorting the set will take O(k * log(k)) time, where k is the number of unique elements in arr which is less than or equal to n. Therefore, this step takes O(n + k * log(k)).

2. [bisect_right(t, x) for x in arr]: For each element x in the original arr, we perform a binary search using bisect_right. Binary search takes O(log(k)) time per search, and since we are performing it for each element n times, this step takes O(n * log(k)) time.

Thus, the overall time complexity is O(n + k * log(k) + n * log(k)), which simplifies to O(n * log(k)) because n will typically be larger than k and hence n * log(k) would be the dominant term.

Space Complexity

The space complexity can be considered as follows:

1. t = sorted(set(arr)): Creating a set and then a sorted list from the array takes O(k) space where k is the number of unique elements.

2. The list comprehension does not use additional space that depends on the size of the input (other than space for the output list, which is always required for the problem). The output list itself takes O(n) space.

In conclusion, the space complexity is O(n + k), which simplifies to O(n) if we do not count the output space as extra space (as is common in complexity analysis), or if we assume that k is at most n.

Learn more about how to find time and space complexity quickly using problem constraints.