#1331

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Rank Transform of an Array

Transform the elements of an array into their ranks, where the rank represents the size order of the elements.

Problem Statement

You are given an array of integers, arr. Your task is to replace each element in the array with its rank in the sorted order of the array. The rank of an element is its position when the array is sorted in ascending order, starting from 1. If two elements are equal, they should have the same rank.

For example, in an array like [40, 10, 20, 30], the rank of 40 is 4 as it is the largest, 10 has rank 1 as it is the smallest, 20 has rank 2, and 30 has rank 3. Ensure that you consider the ranking of identical elements as well.

Examples

Example 1

Input: arr = [40,10,20,30]

Output: [4,1,2,3]

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]

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]

Example details omitted.

Constraints

0 <= arr.length <= 105
-109 <= arr[i] <= 109

Solution Approach

Sort the Array

First, create a copy of the original array and sort it. This helps in determining the relative order of elements. Sorting ensures that elements can be mapped directly to their ranks in ascending order.

Map Sorted Elements to Ranks

Create a hash table to map each element in the sorted array to its rank. This will allow you to assign the rank to each element in the original array quickly using the hash table.

Replace with Rank

Iterate through the original array, and for each element, use the hash table to replace it with its corresponding rank. This avoids unnecessary comparisons and speeds up the process.

Complexity Analysis

Metric	Value
Time	O(N \cdot \log N)
Space	O(N)

The time complexity is dominated by the sorting step, which is O(N * log N), where N is the number of elements in the array. The space complexity is O(N) due to the extra space needed for the sorted array and hash table.

What Interviewers Usually Probe

The candidate is familiar with sorting and hash tables.
The candidate efficiently implements the solution with minimal complexity.
The candidate can handle arrays with duplicate elements correctly.

Common Pitfalls or Variants

Common pitfalls

Not handling duplicates properly and giving them different ranks.
Misunderstanding the requirement to rank based on sorted order rather than the array index.
Not optimizing the solution by using a hash table for quick lookup of ranks.

Follow-up variants

What if the array contains negative numbers?
What if the array has a very large size, like 100,000 elements?
How would you handle ranking based on descending order instead of ascending?

FAQ

What is the rank of an element in the 'Rank Transform of an Array' problem?

The rank of an element is its position when the array is sorted in ascending order, starting from 1.

How do you handle duplicate elements in this problem?

Duplicate elements share the same rank. You can use a hash table to ensure each element maps to the correct rank.

What is the time complexity of the solution?

The time complexity is O(N * log N), dominated by the sorting step.

Can the solution handle arrays with negative numbers?

Yes, the solution works with both positive and negative numbers, as it ranks elements based on their relative size.

What is the space complexity of the solution?

The space complexity is O(N), as extra space is needed for the sorted array and hash table.

terminal

Solution

Solution 1: Discretization

First, we copy an array $t$, then sort and deduplicate it to obtain an array of length $m$ that is strictly monotonically increasing.

1

2

3

4

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        t = sorted(set(arr))
        return [bisect_right(t, x) for x in arr]

Solution 2: Sorting + Hash Map

#### TypeScript

1

2

3

4

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        t = sorted(set(arr))
        return [bisect_right(t, x) for x in arr]

Continue Practicing

#1338 reduce array size to the half #1346 check if n and its double exist #1311 get watched videos by your friends