1331. Rank Transform of an Array

[mah-shamim]

Topics: Array, Hash Table, Sorting

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

Hint:

1. Use a temporary array to copy the array and sort it.
2. The rank of each element is the number of unique elements smaller than it in the sorted array plus one.

[kovatz]

We can break it down into the following steps:

1. Copy and sort the array: This helps in determining the rank of each unique element.
2. Use a hash map to assign ranks to elements: Since multiple elements can share the same value, a hash map (associative array in PHP) will help map each element to its rank.
3. Replace the original elements with their ranks: Using the hash map, we can replace each element in the original array with its corresponding rank.

Let's implement this solution in PHP: 1331. Rank Transform of an Array

<?php
/**
 * @param Integer[] $arr
 * @return Integer[]
 */
function arrayRankTransform($arr) {
    // If the array is empty, return an empty array
    if (empty($arr)) {
        return [];
    }

    // Step 1: Copy the original array and sort it
    $sorted = $arr;
    sort($sorted);
    
    // Step 2: Use a hash map to store the rank of each element
    $rank = array();
    $current_rank = 1;

    foreach ($sorted as $value) {
        // Assign rank only if the element has not been assigned a rank yet
        if (!isset($rank[$value])) {
            $rank[$value] = $current_rank;
            $current_rank++;
        }
    }

    // Step 3: Replace elements in the original array with their ranks
    $result = array();
    foreach ($arr as $value) {
        $result[] = $rank[$value];
    }

    return $result;
}

// Example usage:
$arr1 = [40, 10, 20, 30];
print_r(arrayRankTransform($arr1)); // Output: [4, 1, 2, 3]

$arr2 = [100, 100, 100];
print_r(arrayRankTransform($arr2)); // Output: [1, 1, 1]

$arr3 = [37, 12, 28, 9, 100, 56, 80, 5, 12];
print_r(arrayRankTransform($arr3)); // Output: [5, 3, 4, 2, 8, 6, 7, 1, 3]
?>

Explanation:

1. Copy and sort the array:

   • We create a copy of the input array $sorted and sort it. This helps in determining the rank of each unique element.

2. Assign ranks to elements:

   • We iterate through the sorted array and use a hash map $rank to store the rank of each unique element.
   • We use isset to check if an element has already been assigned a rank. If not, we assign the current rank and increment it.

3. Replace elements with their ranks:

   • We then iterate through the original array and replace each element with its corresponding rank by looking it up in the $rank hash map.

Time Complexity:

• Sorting the array takes O(n log n), where n is the size of the array.
• Assigning ranks and replacing values takes O(n).
• Overall time complexity is O(n log n).

This solution efficiently handles large arrays while maintaining simplicity.

[mah-shamim]

Thanks to solve the "Rank Transform of an Array" problem

[kovatz]

Thanks