1331. Rank Transform of an Array

Description

Given an array of integers, the goal is to transform the array such that each element is replaced by its rank. The rank of an element is its position in the sorted version of the array, where ranks start from 1. If two elements are equal, they should have the same rank.

For example, given the array [40, 10, 20, 30], the sorted array is [10, 20, 30, 40], so the ranks are [4, 1, 2, 3].

Intuition

The core idea is to map each element in the array to its rank, based on the element's position in the sorted version of the array. By maintaining the original indices while sorting, we can ensure that ranks are assigned correctly. Elements with the same value should share the same rank.

Approach

1. Initial Checks: - If the input array is empty, return an empty array. - If the input array has only one element, return [1] since it has the highest and only rank.
2. Mapping Elements to Their Indices: - Create a temporary list containing pairs of elements and their original indices.
3. Sorting: - Sort the array based on the element values.
4. Rank Assignment: - Traverse through the sorted list and assign ranks to the elements in their original positions. - If an element's value is the same as the previous value, it gets the same rank. Otherwise, increment the rank by 1.
5. Output: - Return the transformed array.

Complexity

• Time Complexity: O(n log n) due to the sorting step, where n is the number of elements in the array.
• Space Complexity: O(n) for storing the temporary array of elements and indices.

Code

C++

class Solution {
public:
    std::vector arrayRankTransform(std::vector& arr) {
        if (arr.empty()) return {};

        std::vector> temp;
        for (int i = 0; i < arr.size(); ++i) {
            temp.push_back({arr[i], i});
        }

        std::sort(temp.begin(), temp.end());

        int rank = 1;
        arr[temp[0].second] = rank;

        for (int i = 1; i < temp.size(); ++i) {
            if (temp[i].first != temp[i - 1].first) {
                ++rank;
            }
            arr[temp[i].second] = rank;
        }

        return arr;
    }
};

Python

class Solution:
    def arrayRankTransform(self, arr):
        if not arr:
            return []

        temp = sorted((val, idx) for idx, val in enumerate(arr))

        rank = 1
        arr[temp[0][1]] = rank

        for i in range(1, len(arr)):
            if temp[i][0] != temp[i - 1][0]:
                rank += 1
            arr[temp[i][1]] = rank

        return arr

Java

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        if (arr.length == 0) return new int[]{};
        
        int[][] temp = new int[arr.length][2];
        for (int i = 0; i < arr.length; i++) {
            temp[i][0] = arr[i];
            temp[i][1] = i;
        }

        Arrays.sort(temp, Comparator.comparingInt(a -> a[0]));

        int rank = 1;
        arr[temp[0][1]] = rank;

        for (int i = 1; i < temp.length; i++) {
            if (temp[i][0] != temp[i - 1][0]) {
                rank++;
            }
            arr[temp[i][1]] = rank;
        }

        return arr;
    }
}

JavaScript

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var arrayRankTransform = function (arr) {
    if (arr.length === 0) return [];
    if (arr.length === 1) return [1];

    let temp = arr.map((val, idx) => [val, idx]);
    temp.sort((a, b) => a[0] - b[0]);

    let rank = 1;
    let prev = temp[0][0];
    for (let i = 0; i < arr.length; i++) {
        if (prev < temp[i][0]) {
            rank++;
        }
        arr[temp[i][1]] = rank;
        prev = temp[i][0];
    }

    return arr;
};