1331. Rank Transform of an Array
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 57.3%
Problem Breakdown
The problem requires transforming an array of integers such that each element is replaced by its rank. The rank represents how large the element is, following these rules:
- Rank starts from 1.
- Larger elements have larger ranks.
- Equal elements share the same rank.
- Ranks should be as small as possible.
Inputs:
- An array of integers
arrwhere each element can range from -10^9 to 10^9 and the length of the array can be up to 10^5.
Outputs:
- An array of integers where each integer is replaced by its rank according to the rules specified above.
Implicit Constraints/Edge Cases:
- The array could be empty.
- There could be duplicate elements in the array.
- Negative numbers are allowed.
Intuition
A brute-force approach would involve sorting the array and then iterating through it to assign ranks. However, this approach is inefficient with a time complexity of O(n log n) due to sorting and an additional O(n) for assigning ranks, leading to a total of O(2n log n).
The key insight is that we can use a dictionary (hash map) to store the rank of each unique element as we sort it. This way, we avoid the need for a second pass through the array to assign ranks, reducing the time complexity to O(n log n) primarily due to sorting.
Approach
- Sort the Array: First, sort the array to determine the order of elements.
- Assign Ranks: Use a dictionary to map each unique element to its rank as we iterate through the sorted array.
- Replace Elements with Ranks: Iterate through the original array and replace each element with its corresponding rank from the dictionary.
Data Structures:
- A list to store the sorted version of the input array.
- A dictionary to map elements to their ranks.
Complexity Analysis
- Time Complexity: O(n log n) due to sorting the array. The subsequent operations (assigning ranks and replacing elements) are linear, i.e., O(n).
- Space Complexity: O(n) for storing the sorted array and the dictionary mapping elements to ranks.
Solution
def arrayRankTransform(arr):
# Step 1: Sort the array
sorted_arr = sorted(set(arr))
# Step 2: Create a rank map
rank_map = {val: idx + 1 for idx, val in enumerate(sorted_arr)}
# Step 3: Replace elements with their ranks
return [rank_map[num] for num in arr]
# Example usage:
print(arrayRankTransform([40, 10, 20, 30])) # Output: [4, 1, 2, 3]
print(arrayRankTransform([100, 100, 100])) # Output: [1, 1, 1]
print(arrayRankTransform([37, 12, 28, 9, 100, 56, 80, 5, 12])) # Output: [5, 3, 4, 2, 8, 6, 7, 1, 3]
Edge Cases Handled
- Empty Array: The function will return an empty list as expected.
- All Elements Equal: All elements will have the same rank of 1.
- Negative Numbers: Negative numbers are handled correctly in the sorting and ranking process.