Rank Transform of an Array - Solution & Explanation
Problem Statement
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 Overview
Problem Overview: Given an integer array, replace every element with its rank after sorting the values in ascending order. The smallest value gets rank 1. Equal values share the same rank, and ranks increase only when the value changes.
Approach 1: Sorting and Ranking (O(n log n) time, O(n) space)
This approach sorts the unique values and assigns ranks incrementally. Start by copying the array and sorting it. Then iterate through the sorted list and build a hash table that maps each number to its rank. Only assign a new rank when the current value differs from the previous value so duplicates receive the same rank. Finally, iterate through the original array and replace each value with its stored rank using constant-time hash lookups.
The key insight is separating ordering from mapping. Sorting determines the rank order, while the hash map allows quick translation back to the original positions. This approach works well for most cases and keeps the implementation simple. Time complexity comes from sorting the array (O(n log n)) and the additional passes are linear.
Approach 2: Using Coordinate Compression (O(n log n) time, O(n) space)
Coordinate compression reduces large or scattered values into a compact rank range. First, copy the array and sort it. Remove duplicates from the sorted list so you only keep unique values. Each unique value’s index in this sorted list determines its rank (index + 1). Store these mappings in a dictionary and then transform the original array by replacing each element with its compressed coordinate (rank).
This method is conceptually similar to the first approach but emphasizes the compression idea commonly used in competitive programming and sorting problems. It is especially useful when the input values are very large or sparse but you only care about relative ordering. By compressing them into ranks, you reduce the value domain without losing ordering information.
Both methods rely on sorting to establish global ordering and use a array traversal to rebuild the result. The difference is mainly conceptual: the first focuses on ranking while the second frames the process as coordinate compression.
Recommended for interviews: The sorting + hash map solution is the most direct and the one interviewers typically expect. It clearly demonstrates understanding of ordering, duplicate handling, and efficient lookups. Mentioning coordinate compression shows deeper algorithmic awareness, especially in problems involving large ranges or index remapping.
Approach 1: Sorting and Ranking
This approach involves sorting the array to determine the rank of each element. After sorting, unique elements are mapped to their ranks.
The C solution involves sorting the array and creating a map of ranks. Sorted unique elements are assigned ranks incrementally. The original elements are then mapped to their ranks using this mapping.
Complexity
Time Complexity: O(N log N) due to sorting.
Space Complexity: O(N) for storing the sorted array and rank map.
Approach 2: Using Coordinate Compression
Coordinate compression is a method to map large ranges of numbers to smaller ranges, maintaining their relative order. This approach uses this idea to assign ranks.
The C coordinate compression solution involves sorting the array and creating a rank map by compressing coordinates. This map is used for rank assignment efficiently.
Complexity
Time Complexity: O(N log N) due to sorting and binary search operations.
Space Complexity: O(N) for rank maps.
Approach 3: Discretization
First, we copy an array t, then sort and deduplicate it to obtain an array of length m that is strictly monotonically increasing.
Next, we traverse the original array arr. For each element x in the array, we use binary search to find the position of x in t. The position plus one is the rank of x.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array arr.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Sorting + Hash Map
Code
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sorting and Ranking | Time Complexity: O(N log N) due to sorting. |
| Using Coordinate Compression | Time Complexity: O(N log N) due to sorting and binary search operations. |
| Discretization | — |
| Sorting + Hash Map | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Ranking with Hash Map | O(n log n) | O(n) | General case. Clear implementation and easy to explain during interviews. |
| Coordinate Compression | O(n log n) | O(n) | Useful when values are large or sparse and you want to remap them into a compact rank range. |
Video Solution
Rank Transform of an Array | Leetcode 1331 • Techdose • 7,777 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Rank Transform of an Array easy or hard?
How to solve Rank Transform of an Array in O(n)?
Rank Transform of an Array Python or Java solution?
What is the best approach for Rank Transform of an Array?
What data structure is used in Rank Transform of an Array?
What is the time complexity of Rank Transform of an Array?
Is Rank Transform of an Array asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Rank Transform of an Array with our built-in code editor and test cases.
Practice on FleetCode