1331. Rank Transform of an Array - Detailed Explanation
Problem Statement
Given an array of integers arr, replace each element with its rank when the array is sorted in ascending order. The smallest number should have rank 1, the second smallest rank 2, and so on. If two numbers are the same, they receive the same rank.
Example 1:
- Input:
arr = [40, 10, 20, 30] - Output:
[4, 1, 2, 3] - Explanation:
- Sorting
[40, 10, 20, 30]gives[10, 20, 30, 40]. - Assign ranks:
10 -> 1,20 -> 2,30 -> 3,40 -> 4. - Replace elements in the original array:
[4, 1, 2, 3].
- Sorting
Example 2:
- Input:
arr = [100, 100, 100] - Output:
[1, 1, 1] - Explanation:
- Sorting
[100, 100, 100]gives[100](unique values). - Assign rank:
100 -> 1. - Replace elements in the original array:
[1, 1, 1].
- Sorting
Constraints:
0 <= arr.length <= 10^5-10^9 <= arr[i] <= 10^9
Hints to Solve the Problem
- Sorting can help: If we sort the array (or a copy of it), we can determine the rank of each element based on its sorted position.
- Use a mapping: After sorting, store each unique element’s rank in a dictionary (or hash map) for quick lookup. This avoids recomputing ranks for duplicate values and makes replacing the values efficient.
Approach 1: Brute Force (Sorting and Map)
Idea: Make a sorted copy of the array to determine the rank of each element, then replace each element in the original array with its rank. We use a hash map to store ranks for quick lookup, which also ensures duplicates get the same rank.
Explanation:
- Sort a copy of the array: Create a sorted version of the array (ascending order) without modifying the original.
- Assign ranks to unique values: Traverse the sorted array and assign rank
1to the smallest element, rank2to the second smallest, and so on. Use a dictionary (rank_map) to map each unique number to its rank. If a number is the same as the previous (duplicate), it will already have a rank in the map (so skip assigning a new rank). - Replace with ranks: Iterate over the original array and replace each element with its corresponding rank from the dictionary.
This approach ensures that equal elements receive the same rank since the map will assign a rank only the first time a number is seen. The overall time complexity is dominated by sorting.
Python Code:
Java Code:
Complexity Analysis: Sorting the array takes O(N log N) time. Assigning ranks and then transforming the original array are O(N) operations. Therefore, the overall time complexity is O(N log N). Space complexity is O(N) for storing the sorted copy and the rank map.
Approach 2: Optimized Using Sorting and HashMap (Efficient Lookup)
Idea: Instead of iterating over the entire sorted array (including duplicates), we can optimize by sorting only the unique values of the array. This directly gives each unique value’s rank position. We then use a hash map to assign these ranks and transform the original array. This approach is more concise and skips redundant processing of duplicate elements. It is essentially performing coordinate compression – replacing each number with its position in the sorted order of unique values.
Explanation:
-
Sort unique values: Extract the set of unique elements from
arrand sort it. For example, ifarr = [40, 10, 20, 30], the unique sorted values are[10, 20, 30, 40]. -
Map each value to its rank: Iterate over this sorted list of unique values and assign ranks starting from 1. Store these in a hash map (
rank_map) where each number maps to its rank. (e.g.,{10: 1, 20: 2, 30: 3, 40: 4}). -
Replace original elements: Go through the original array and replace each element with its rank by looking up the value in
rank_map.
This method avoids assigning a new rank for duplicates (since duplicates aren’t in the unique list more than once). The time complexity remains O(N log N) due to sorting the unique values (which in worst case is still N if all values are distinct). Dictionary lookups for replacement are O(1) on average.
Python Code:
Java Code:
Complexity Analysis: Extracting unique values and sorting them takes O(N log N) in the worst case. Creating the rank map and transforming the array are O(N). Thus, overall complexity is O(N log N). This is optimal for the given problem constraints. Space complexity is O(N) for the map and the array of unique values.
Edge Cases
Consider the following edge cases to ensure the solution handles them correctly:
-
Empty Array: If
arr = [], the result should be an empty list[](no elements to rank). -
Single Element: If
arr = [5], the result should be[1]since the single element is the smallest (and only) element, so its rank is 1. -
All Elements Identical: If
arr = [100, 100, 100], the result should be[1, 1, 1]because identical elements share the same rank (all are smallest and largest simultaneously, rank 1). -
Large Range of Values: The solution should handle very large or very small integers (e.g., negatives and positives up to 10^9) since it does not rely on the actual magnitude of values — only their relative order. Sorting will correctly order them, and using a hash map for ranks is unaffected by the numeric range.
Common Mistakes
-
Forgetting duplicate handling: A common mistake is assigning new ranks to duplicate values. Make sure that if a number has already been seen (and given a rank), you do not assign it a new rank again. Using a hash map (or checking the previous value during sorting) prevents this issue.
-
Altering the original array unintentionally: If you sort the array in place without using a copy, you might lose the original order needed to map back ranks. Always use a sorted copy or sort a list of unique values, so the original array remains intact for the final transformation.
-
Assuming ranks start at 0: Remember that by definition, ranks in this problem start at 1 for the smallest element. Off-by-one errors can happen if you use zero-based indexing for ranks. (Our approaches handle this by starting rank count at 1 or adding 1 to indices.)
Related Problems
-
Relative Ranks: Similar idea of ranking, but applied to athletes’ scores (LeetCode “Relative Ranks” problem assigns Gold/Silver/Bronze for top 3 and numeric ranks for others). It involves sorting scores and then outputting ranks/medals accordingly.
-
Sort Characters by Frequency: In this problem, characters are sorted based on frequency counts. Although different in context, it also uses sorting (by frequency) and possibly a hash map to organize the output.
-
Top K Frequent Elements: Requires finding the most frequent elements in an array. It can be solved using hash maps for frequency and then using a heap or sorting by frequency. This is another scenario of using sorting + maps for ranking or ordering elements based on some metric.
The above approaches both run in efficient O(N log N) time and use extra space proportional to O(N), which is acceptable given the problem constraints. They ensure that equal elements receive equal ranks and that ranks are in the correct 1-indexed order. This technique of mapping values to their sorted order is a form of coordinate compression, which preserves the relative order of values while reducing them to a compact range. The provided solutions are straightforward and should work well for all valid inputs.
GET YOUR FREE
Coding Questions Catalog
