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.
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: Same elements share 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 <= 105-109 <= arr[i] <= 109
Approach 01:
-
C++
-
Python
class Solution {
public:
std::vector<int> arrayRankTransform(std::vector<int>& numbers) {
std::vector<int> sortedNumbers(numbers);
std::unordered_map<int, int> numberRank;
std::ranges::sort(sortedNumbers);
for (const int number : sortedNumbers) {
if (!numberRank.contains(number)) {
numberRank[number] = numberRank.size() + 1;
}
}
for (int& number : numbers) {
number = numberRank[number];
}
return numbers;
}
};
Time Complexity
- Sorting the array:
Sorting the
sortedNumbersvector usingstd::ranges::sorttakes \(O(n \log n)\), where \(n\) is the number of elements in thenumbersvector. - Building the rank map:
Iterating through the sorted array and filling the
numberRankunordered map takes \(O(n)\), where \(n\) is the size of the array. Each insertion and lookup operation in the unordered map takes average \(O(1)\) time. - Transforming the input array:
Iterating through the original array to replace each number with its rank also takes \(O(n)\).
- Overall Time Complexity:
The overall time complexity is \(O(n \log n)\), dominated by the sorting step.
Space Complexity
- Auxiliary Space:
The function uses extra space for the
sortedNumbersvector, which is a copy of the input array, and thenumberRankunordered map. Both require \(O(n)\) space, where \(n\) is the size of the array. - Overall Space Complexity:
The overall space complexity is \(O(n)\), where \(n\) is the number of elements in the input array.
class Solution:
def arrayRankTransform(self, numbers: List[int]) -> List[int]:
sortedNumbers = sorted(numbers)
numberRank = {}
for number in sortedNumbers:
if number not in numberRank:
numberRank[number] = len(numberRank) + 1
return [numberRank[number] for number in numbers]
Time Complexity
- Sorting the array:
Sorting the input array
numberstakes \(O(n \log n)\), where \(n\) is the number of elements in the array. - Building the rank map:
Iterating through the sorted array and creating the
numberRankdictionary takes \(O(n)\), where \(n\) is the size of the array. Each lookup and insertion into the dictionary takes average \(O(1)\) time. - Creating the result array:
Building the result array by looking up the ranks from
numberRankalso takes \(O(n)\) time. - Overall Time Complexity:
The overall time complexity is \(O(n \log n)\), dominated by the sorting step.
Space Complexity
- Auxiliary Space:
The function uses extra space for the
sortedNumberslist and thenumberRankdictionary. The size of both structures is proportional to the number of elements in the input array, so they require \(O(n)\) space. - Overall Space Complexity:
The overall space complexity is \(O(n)\), where \(n\) is the number of elements in the input array.