Problem Description

You are given an array of integers arr. Your task is to replace each element in the array with its rank according to specific rules.

The rank represents the relative size of each element compared to other elements in the array. The ranking rules are:

1. Rank starts from 1: The smallest element gets rank 1, the next smallest gets rank 2, and so on.

2. Larger elements get larger ranks: If element A is greater than element B, then A's rank must be greater than B's rank.

3. Equal elements get equal ranks: If two or more elements have the same value, they must receive the same rank.

4. Ranks should be consecutive: The ranks should use the smallest possible integers. For example, if you have values [10, 20, 20, 30], the ranks would be [1, 2, 2, 3] not [1, 2, 2, 4].

For example:

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

• Output: [4, 1, 2, 3]

• Explanation: 10 is the smallest (rank 1), 20 is second smallest (rank 2), 30 is third (rank 3), and 40 is the largest (rank 4).

• Input: arr = [100, 100, 100]

• Output: [1, 1, 1]

• Explanation: All elements are equal, so they all get rank 1.

The solution uses discretization by creating a sorted array of unique values from the original array. Then for each element in the original array, it finds its position in this sorted unique array using binary search (bisect_right), which directly gives the rank.

Intuition

The key insight is recognizing that ranks are essentially the position of each element when all unique values are sorted in ascending order.

Think about it this way: if we line up all the distinct values from smallest to largest, the rank of any element is simply its position in this lineup. For example, with values [40, 10, 20, 30], the unique sorted values are [10, 20, 30, 40]. The element 10 is at position 1, 20 is at position 2, and so on.

But what about duplicate values? Since equal elements must have the same rank, we only need to consider unique values when determining ranks. This naturally handles the duplicate case - if we have [20, 10, 20, 30], we create a sorted unique list [10, 20, 30], and both occurrences of 20 will map to the same position (rank 2).

This leads us to a two-step approach:

1. Extract all unique values and sort them - this gives us the "rank mapping"
2. For each element in the original array, find where it sits in this sorted unique list

The beauty of using bisect_right is that it returns the insertion point that would maintain sorted order, which is exactly the count of elements less than or equal to the target value. This count is precisely the rank we need! For instance, if bisect_right([10, 20, 30], 20) returns 2, it means there are 2 elements ≤ 20, making 20's rank equal to 2.

This approach elegantly satisfies all requirements: ranks start from 1 (since bisect_right returns indices starting from 0 for non-existent smaller elements, and we get 1 for the smallest element), larger elements get larger ranks (guaranteed by the sorted order), and equal elements get equal ranks (they map to the same position in the sorted unique array).

Learn more about Sorting patterns.

Solution Approach

The solution implements the discretization technique to transform array values into ranks. Here's the step-by-step implementation:

Step 1: Create a sorted unique array

t = sorted(set(arr))

• set(arr) removes all duplicate values from the original array
• sorted() arranges these unique values in ascending order
• This creates our "rank mapping" array t where the position of each value determines its rank

For example, if arr = [40, 10, 20, 30, 20]:

• set(arr) gives us {10, 20, 30, 40}
• sorted(set(arr)) gives us [10, 20, 30, 40]

Step 2: Map each element to its rank using binary search

return [bisect_right(t, x) for x in arr]

• For each element x in the original array
• bisect_right(t, x) performs binary search to find the rightmost insertion position of x in the sorted array t
• This position equals the number of unique values less than or equal to x, which is exactly the rank

The bisect_right function returns:

• For x = 10: position 1 (since 10 is at index 0, and bisect_right returns the position after the last occurrence)
• For x = 20: position 2
• For x = 30: position 3
• For x = 40: position 4

Time Complexity: O(n log n) where n is the length of the array

• Creating the set: O(n)
• Sorting unique elements: O(m log m) where m ≤ n is the number of unique elements
• Binary search for each element: O(n log m)
• Overall: O(n log n) dominated by sorting

Space Complexity: O(m) where m is the number of unique elements in the array for storing the sorted unique array t

The elegance of this approach lies in how bisect_right naturally handles all the ranking rules - it automatically assigns consecutive ranks starting from 1, maintains order relationships, and gives equal elements the same rank since they map to the same position in the sorted unique array.

Example Walkthrough

Let's walk through the solution with the array arr = [30, 10, 30, 20].

Step 1: Create sorted unique array

• Start with: arr = [30, 10, 30, 20]
• Extract unique values: set(arr) = {10, 20, 30}
• Sort them: t = [10, 20, 30]

Now we have our rank mapping where:

• Position 1 → value 10 (smallest)
• Position 2 → value 20 (middle)
• Position 3 → value 30 (largest)

Step 2: Find rank for each original element

Process each element in the original array [30, 10, 30, 20]:

1. First element: 30

   • Use bisect_right(t, 30) where t = [10, 20, 30]
   • Binary search finds 30 at index 2
   • bisect_right returns the position after the last occurrence: 3
   • Rank of 30 is 3

2. Second element: 10

   • Use bisect_right(t, 10) where t = [10, 20, 30]
   • Binary search finds 10 at index 0
   • bisect_right returns the position after the last occurrence: 1
   • Rank of 10 is 1

3. Third element: 30

   • Use bisect_right(t, 30) where t = [10, 20, 30]
   • Same as before, returns 3
   • Rank of 30 is 3 (same as the first 30, satisfying the equal elements rule)

4. Fourth element: 20

   • Use bisect_right(t, 20) where t = [10, 20, 30]
   • Binary search finds 20 at index 1
   • bisect_right returns the position after the last occurrence: 2
   • Rank of 20 is 2

Final Result: [3, 1, 3, 2]

This correctly assigns:

• Rank 1 to the smallest value (10)
• Rank 2 to the middle value (20)
• Rank 3 to the largest value (30)
• Both occurrences of 30 get the same rank (3)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity breaks down as follows:

• set(arr): O(n) to create a set from the array
• sorted(set(arr)): O(m × log m) where m is the number of unique elements. In the worst case, m = n, so this is O(n × log n)
• List comprehension with bisect_right: For each of the n elements in arr, we perform a binary search using bisect_right on the sorted array t of size m. Each binary search takes O(log m) time. Total: O(n × log m), which is O(n × log n) in the worst case

The dominant operation is either the sorting step or the binary search step, both of which are O(n × log n) in the worst case.

Space Complexity: O(n)

The space complexity consists of:

• set(arr): O(m) space where m ≤ n
• sorted(set(arr)): Creates a new list t of size m, requiring O(m) space
• Output list from the list comprehension: O(n) space

In the worst case where all elements are unique, m = n, giving us O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusion Between bisect_left and bisect_right

A common mistake is using bisect_left instead of bisect_right, which would produce incorrect results.

Why this happens:

• bisect_left(t, x) returns the leftmost position where x should be inserted
• bisect_right(t, x) returns the rightmost position where x should be inserted

Example demonstrating the issue:

arr = [20, 10, 20, 30]
unique_sorted = [10, 20, 30]  # sorted unique values

# Using bisect_left (WRONG):
# bisect_left(unique_sorted, 10) = 0  → rank would be 0 (incorrect!)
# bisect_left(unique_sorted, 20) = 1  → rank would be 1
# bisect_left(unique_sorted, 30) = 2  → rank would be 2

# Using bisect_right (CORRECT):
# bisect_right(unique_sorted, 10) = 1  → rank is 1 ✓
# bisect_right(unique_sorted, 20) = 2  → rank is 2 ✓
# bisect_right(unique_sorted, 30) = 3  → rank is 3 ✓

Solution: Always use bisect_right for ranking problems since it naturally provides 1-based indexing. The rightmost position after an element equals the count of elements less than or equal to it.

Pitfall 2: Attempting Manual Rank Assignment with Duplicates

Some might try to manually assign ranks while iterating through sorted elements, leading to complex logic for handling duplicates:

Incorrect approach:

def arrayRankTransform(arr):
    if not arr:
        return []
  
    sorted_arr = sorted(enumerate(arr), key=lambda x: x[1])
    ranks = [0] * len(arr)
    current_rank = 1
  
    # This gets complicated with duplicates
    for i in range(len(sorted_arr)):
        if i > 0 and sorted_arr[i][1] != sorted_arr[i-1][1]:
            current_rank += 1  # Wrong! Should increment by unique count
        ranks[sorted_arr[i][0]] = current_rank
  
    return ranks

Problems with this approach:

• Requires careful tracking of when to increment ranks
• Easy to make off-by-one errors
• More complex code that's harder to debug

Solution: Use the discretization approach with sorted(set(arr)) and bisect_right. This automatically handles all edge cases and duplicate values without special logic.

Pitfall 3: Not Handling Empty Arrays

The code might fail or behave unexpectedly with empty input arrays.

Test case:

arr = []
unique_sorted = sorted(set([]))  # Returns []
result = [bisect_right([], x) for x in []]  # Returns []

While the current implementation handles this correctly, it's important to be aware that:

• sorted(set([])) returns an empty list
• List comprehension over an empty list returns an empty list
• bisect_right is never called, avoiding any potential issues

Solution: The current implementation naturally handles empty arrays, but for clarity and defensive programming, you might want to add an explicit check:

def arrayRankTransform(self, arr: List[int]) -> List[int]:
    if not arr:
        return []
  
    unique_sorted = sorted(set(arr))
    return [bisect_right(unique_sorted, x) for x in arr]