EasyNo. 1331
Rank Transform of an Array — LeetCode 1331 Python Solution
- Pattern
- Sorting
- Topics
- Array, Hash Table, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given an array of integers arr, replace each element with its rank. The rank represents how large the element is.
Example
- 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.
Python solution
class Solution:
def arrayRankTransform(self, arr: List[int]) -> List[int]:
t = sorted(set(arr))
return [bisect_right(t, x) for x in arr]Complexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1331. Rank Transform of an Array is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1338 | Reduce Array Size to The Half | Medium |
| 0049 | Group Anagrams | Medium |
| 0169 | Majority Element | Easy |
| 0217 | Contains Duplicate | Easy |
| 0229 | Majority Element II | Medium |
| 0268 | Missing Number | Easy |
Frequently asked questions
- How hard is LeetCode 1331. Rank Transform of an Array?
LeetCode 1331. Rank Transform of an Array is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1331. Rank Transform of an Array?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 1331. Rank Transform of an Array?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1331. Rank Transform of an Array cover?
LeetCode 1331. Rank Transform of an Array is tagged Array, Hash Table and Sorting on LeetCode.