Domain 1EasyCORE

Rank Transform of an Array

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

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 arr where 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

  1. Sort the Array: First, sort the array to determine the order of elements.
  2. Assign Ranks: Use a dictionary to map each unique element to its rank as we iterate through the sorted array.
  3. 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.