1331. Rank Transform of an Array

Array
Hash Table
Sorting

TIME

O(n log n)

SPACE

O(n)

Intuition

The rank of a value is simply its 1-based position among the distinct sorted values: the smallest distinct value is rank 1, the next distinct value rank 2, and so on. Equal elements naturally share a rank.

Approach

Take the sorted set of distinct values in arr.
Map each distinct value to its index + 1 (its rank).
Replace every element of arr with its mapped rank.

Complexity

Time: O(n log n), sorting the distinct values
Space: O(n), the value→rank map

Edge Cases

Empty array → empty output
All equal → all rank 1
Duplicates map to the same rank (Example 3)
Negative values handled the same way (ordering is numeric)

Code

from typing import List


class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        """
        1331. Rank Transform of an Array
        Time: O(n log n)
        Space: O(n)
        """
        rank = {v: i + 1 for i, v in enumerate(sorted(set(arr)))}
        return [rank[v] for v in arr]

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 1331. Rank Transform of an Array
 * Time: O(n log n)
 * Space: O(n)
 */
class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int[] sorted = arr.clone();
        Arrays.sort(sorted);

        // Map each distinct value to its 1-based rank.
        Map<Integer, Integer> rank = new HashMap<>();
        int r = 1;
        for (int v : sorted) {
            if (!rank.containsKey(v)) {
                rank.put(v, r++);
            }
        }

        int[] result = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            result[i] = rank.get(arr[i]);
        }
        return result;
    }
}