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 thebisect
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 listarr
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 forx
int
to the right of any existing entries. Essentially, it finds the index of the first element in the sorted listt
that is greater thanx
.
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 int
). - If elements in
arr
are equal, they will have the same rank sincebisect_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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
Convert to set:
1{10, 20, 40}
This set does not include duplicates and now contains only the unique values
10
,20
, and40
. -
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
inarr
,bisect_right(t, 40)
returns3
because there are two elements int
that are less than or equal to40
. Hence, its rank is3
. - For the element
20
inarr
,bisect_right(t, 20)
returns2
, as there is only one element less than or equal to20
. Hence, its rank is2
. - For the first
10
inarr
,bisect_right(t, 10)
returns1
, since there are no elements int
that are less than10
. Hence, its rank is1
. - The second
10
inarr
will have the same rank as the first10
since they are equal. Therefore,bispect_right(t, 10)
again returns1
.
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
1from typing import List
2from bisect import bisect_right
3
4class Solution:
5 def arrayRankTransform(self, arr: List[int]) -> List[int]:
6 # Create a sorted list of the unique elements in `arr`
7 unique_sorted_arr = sorted(set(arr))
8
9 # For every element 'x' in `arr`, find its rank. The rank is determined by the
10 # position of 'x' in the `unique_sorted_arr` plus one because bisect_right will
11 # give us the insertion point which is the number of elements that are less than or equal to 'x'.
12 # Since ranks are 1-indexed, the position itself is the rank.
13 ranks = [bisect_right(unique_sorted_arr, x) for x in arr]
14
15 # Return the list of ranks corresponding to each element in `arr`
16 return ranks
17
1class Solution {
2
3 public int[] arrayRankTransform(int[] arr) {
4 // Get the size of the input array
5 int arrayLength = arr.length;
6
7 // Create a copy of the array to sort and find unique elements
8 int[] sortedArray = arr.clone();
9 Arrays.sort(sortedArray);
10
11 // This will be the actual size of the array of unique elements
12 int uniqueSize = 0;
13
14 // Loop through the sorted array to filter out the duplicates
15 for (int i = 0; i < arrayLength; ++i) {
16 // If it's the first element or it's different from the previous, keep it
17 if (i == 0 || sortedArray[i] != sortedArray[i - 1]) {
18 sortedArray[uniqueSize++] = sortedArray[i];
19 }
20 }
21
22 // Create an array to hold the answers
23 int[] ranks = new int[arrayLength];
24
25 // Assign the rank to each element in the original array
26 for (int i = 0; i < arrayLength; ++i) {
27 // Binary search finds the index of the current element in the unique array
28 // Since array indexing starts at 0, add 1 to get the correct rank
29 ranks[i] = Arrays.binarySearch(sortedArray, 0, uniqueSize, arr[i]) + 1;
30 }
31
32 // Return the ranks array containing the ranks of each element in arr
33 return ranks;
34 }
35}
36
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to transform an array into ranks of elements
7 vector<int> arrayRankTransform(vector<int>& arr) {
8 // Create a copy of the original array to sort and find unique elements
9 vector<int> sortedArr = arr;
10 sort(sortedArr.begin(), sortedArr.end());
11 // Remove duplicates from sortedArr to get only unique elements
12 sortedArr.erase(unique(sortedArr.begin(), sortedArr.end()), sortedArr.end());
13
14 // Prepare a vector to store the answer
15 vector<int> ranks;
16 // For each element in the original array, find its rank
17 for (int element : arr) {
18 // Find the position (rank) of the element in the sorted unique array
19 // The rank is the index + 1 because ranks are 1-based
20 int rank = upper_bound(sortedArr.begin(), sortedArr.end(), element) - sortedArr.begin();
21 ranks.push_back(rank);
22 }
23 // Return the vector of ranks corresponding to the original array's elements
24 return ranks;
25 }
26};
27
1function arrayRankTransform(arr: number[]): number[] {
2 // Sort the array while preserving the original via spreading
3 const sortedUniqueElements = [...arr].sort((a, b) => a - b);
4 let uniqueCounter = 0;
5
6 // Count unique elements in the sorted array
7 for (let i = 0; i < sortedUniqueElements.length; ++i) {
8 if (i === 0 || sortedUniqueElements[i] !== sortedUniqueElements[i - 1]) {
9 sortedUniqueElements[uniqueCounter++] = sortedUniqueElements[i];
10 }
11 }
12
13 // Binary search function to find the rank of an element
14 const binarySearch = (sortedArray: number[], arrayLength: number, target: number) => {
15 let leftIndex = 0;
16 let rightIndex = arrayLength;
17 while (leftIndex < rightIndex) {
18 const midIndex = (leftIndex + rightIndex) >> 1;
19 if (sortedArray[midIndex] >= target) {
20 rightIndex = midIndex;
21 } else {
22 leftIndex = midIndex + 1;
23 }
24 }
25 return leftIndex + 1; // The rank is index + 1
26 };
27
28 // Create an array for the answer
29 const ranks: number[] = [];
30
31 // Compute the rank for each element in the original array
32 for (const element of arr) {
33 ranks.push(binarySearch(sortedUniqueElements, uniqueCounter, element));
34 }
35
36 // Return the array of ranks
37 return ranks;
38}
39
Time and Space Complexity
Time Complexity
The time complexity of the given code can be broken down into the following parts:
-
sorted(set(arr))
: Creating a set from the array removes duplicates and takesO(n)
time, wheren
is the number of elements inarr
. Sorting the set will takeO(k * log(k))
time, wherek
is the number of unique elements inarr
which is less than or equal ton
. Therefore, this step takesO(n + k * log(k))
. -
[bisect_right(t, x) for x in arr]
: For each elementx
in the originalarr
, we perform a binary search usingbisect_right
. Binary search takesO(log(k))
time per search, and since we are performing it for each elementn
times, this step takesO(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:
-
t = sorted(set(arr))
: Creating a set and then a sorted list from the array takesO(k)
space wherek
is the number of unique elements. -
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.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.