LeetCode 1331 - Rank Transform of an Array

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The problem asks us to replace every number in the input array with its rank when the array is sorted in ascending order.

A rank is defined by the relative ordering of the values:

The smallest unique value gets rank 1
The second smallest unique value gets rank 2
Equal values must receive the same rank
Ranks should be consecutive and as small as possible

The input is an integer array arr, and the output should be another array of the same length where each element has been replaced by its corresponding rank.

For example, consider:

arr = [40, 10, 20, 30]

If we sort the unique values:

[10, 20, 30, 40]

Then their ranks become:

10 -> 1
20 -> 2
30 -> 3
40 -> 4

Applying those mappings back to the original order produces:

[4, 1, 2, 3]

The constraints are important:

The array can contain up to 10^5 elements
Values can range from -10^9 to 10^9

Because the input can be very large, we need an algorithm better than quadratic time. Any approach that compares every element against every other element directly will be too slow.

There are several important edge cases to keep in mind:

An empty array should return an empty array
Arrays where all elements are identical should assign rank 1 everywhere
Negative numbers must still be ranked correctly
Duplicate values must always share the same rank
Very large arrays require an efficient sorting-based solution

Approaches

Brute Force Approach

A straightforward approach is to compute the rank for every element independently.

For each element in the array, we could count how many distinct values are smaller than it. The rank would then be:

(number of distinct smaller elements) + 1

For example:

arr = [40, 10, 20, 30]

For 40, the smaller distinct values are:

[10, 20, 30]

So its rank is 4.

This works correctly because rank is determined entirely by how many unique values are smaller.

However, this approach is inefficient. For every element, we may scan the entire array again to determine smaller unique values. That leads to approximately O(n^2) time complexity, which is too slow for 10^5 elements.

Optimal Approach

The key observation is that ranking only depends on the sorted order of the unique values.

Instead of computing ranks repeatedly, we can:

Extract all unique values
Sort them
Assign ranks sequentially
Store the mapping in a hash map
Replace each original value using the map

This is efficient because sorting the unique values immediately gives us the exact ranking order.

A hash map allows constant-time lookup when converting the original array into ranks.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Compare each element against all others
Optimal	O(n log n)	O(n)	Sort unique values once, then map ranks

Algorithm Walkthrough

Optimal Algorithm

Create a set from the input array.

The set removes duplicates automatically. Since equal values share the same rank, we only care about unique numbers when assigning ranks. 2. Sort the unique values in ascending order.

Sorting establishes the correct ranking order. The smallest number should receive rank 1, the next smallest should receive rank 2, and so on. 3. Create a hash map to store ranks.

Iterate through the sorted unique values and assign ranks sequentially.

Example:

sorted_unique = [10, 20, 30, 40]

Build:

Traverse the original array.

For each value, look up its rank in the hash map and append it to the result array. 5. Return the result.

Why it works

The algorithm works because sorting the unique values produces the exact order required by the ranking rules. Every smaller unique number appears before larger numbers in the sorted list. Assigning ranks sequentially guarantees that:

Smaller values receive smaller ranks
Equal values receive identical ranks
Ranks remain consecutive and minimal

The hash map preserves this relationship and allows efficient reconstruction of the transformed array.

Python Solution

from typing import List

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        # Get all unique values and sort them
        sorted_unique = sorted(set(arr))

        # Assign ranks starting from 1
        rank_map = {}

        for index, value in enumerate(sorted_unique):
            rank_map[value] = index + 1

        # Replace each value with its rank
        result = []

        for value in arr:
            result.append(rank_map[value])

        return result

The implementation begins by converting the array into a set to remove duplicates. This is important because equal values must share the same rank.

Next, the unique values are sorted. Their positions in sorted order directly determine their ranks.

A dictionary called rank_map stores the mapping from value to rank. Using enumerate, we assign ranks beginning at 1.

Finally, we iterate through the original array and replace every value with its mapped rank. Since dictionary lookup is constant time on average, this step is very efficient.

Go Solution

package main

import "sort"

func arrayRankTransform(arr []int) []int {
    // Handle empty input
    if len(arr) == 0 {
        return []int{}
    }

    // Create a set of unique values
    uniqueSet := make(map[int]bool)

    for _, value := range arr {
        uniqueSet[value] = true
    }

    // Convert set to slice
    uniqueValues := make([]int, 0, len(uniqueSet))

    for value := range uniqueSet {
        uniqueValues = append(uniqueValues, value)
    }

    // Sort unique values
    sort.Ints(uniqueValues)

    // Assign ranks
    rankMap := make(map[int]int)

    for index, value := range uniqueValues {
        rankMap[value] = index + 1
    }

    // Build result
    result := make([]int, len(arr))

    for index, value := range arr {
        result[index] = rankMap[value]
    }

    return result
}

The Go solution follows the same overall algorithm as the Python version.

Since Go does not have a built-in set type, a map[int]bool is used to simulate one. Unique values are collected into a slice, sorted using sort.Ints, and then mapped to ranks.

The result slice is preallocated with the correct length for efficiency.

Go slices naturally handle empty arrays, so returning an empty slice for empty input is straightforward.

Worked Examples

Example 1

Input: [40,10,20,30]

Step 1: Extract unique values

Original Array
[40,10,20,30]

Unique values:

{40,10,20,30}

Step 2: Sort unique values

Sorted Unique Values
[10,20,30,40]

Step 3: Assign ranks

Value	Rank
10	1
20	2
30	3
40	4

Step 4: Build result

Original Value	Rank
40	4
10	1
20	2
30	3

Final result:

[4,1,2,3]

Example 2

Input: [100,100,100]

Step 1: Extract unique values

{100}

Step 2: Sort unique values

[100]

Step 3: Assign ranks

Value	Rank
100	1

Step 4: Build result

Original Value	Rank
100	1
100	1
100	1

Final result:

[1,1,1]

Example 3

Input: [37,12,28,9,100,56,80,5,12]

Step 1: Extract unique values

{37,12,28,9,100,56,80,5}

Step 2: Sort unique values

Sorted Unique Values
[5,9,12,28,37,56,80,100]

Step 3: Assign ranks

Value	Rank
5	1
9	2
12	3
28	4
37	5
56	6
80	7
100	8

Step 4: Build result

Original Value	Rank
37	5
12	3
28	4
9	2
100	8
56	6
80	7
5	1
12	3

Final result:

[5,3,4,2,8,6,7,1,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting the unique values dominates the runtime
Space	O(n)	Additional storage for the set, map, and result

The most expensive operation is sorting the unique elements. In the worst case, all elements are distinct, so sorting requires O(n log n) time.

The hash map, set, and output array each require additional memory proportional to the number of elements, resulting in O(n) space complexity.

Test Cases

solution = Solution()

# Provided examples
assert solution.arrayRankTransform([40, 10, 20, 30]) == [4, 1, 2, 3]  # basic ranking
assert solution.arrayRankTransform([100, 100, 100]) == [1, 1, 1]  # all duplicates
assert solution.arrayRankTransform([37,12,28,9,100,56,80,5,12]) == [5,3,4,2,8,6,7,1,3]  # mixed values

# Empty array
assert solution.arrayRankTransform([]) == []  # no elements

# Single element
assert solution.arrayRankTransform([7]) == [1]  # smallest possible non-empty input

# Negative numbers
assert solution.arrayRankTransform([-10, -20, -30]) == [3, 2, 1]  # negative ordering

# Mixed negative and positive
assert solution.arrayRankTransform([-5, 0, 5]) == [1, 2, 3]  # cross-zero ordering

# Duplicate values
assert solution.arrayRankTransform([5, 5, 1, 1, 3]) == [3, 3, 1, 1, 2]  # repeated groups

# Already sorted
assert solution.arrayRankTransform([1, 2, 3, 4]) == [1, 2, 3, 4]  # increasing order

# Reverse sorted
assert solution.arrayRankTransform([4, 3, 2, 1]) == [4, 3, 2, 1]  # decreasing order

# Large integer values
assert solution.arrayRankTransform([10**9, -10**9]) == [2, 1]  # constraint boundaries

Test	Why
`[40,10,20,30]`	Validates standard ranking behavior
`[100,100,100]`	Ensures duplicates share ranks
`[37,12,28,9,100,56,80,5,12]`	Tests mixed ordering and duplicates
`[]`	Validates empty input handling
`[7]`	Confirms single element behavior
`[-10,-20,-30]`	Ensures negative values sort correctly
`[-5,0,5]`	Tests ordering across negative and positive values
`[5,5,1,1,3]`	Verifies repeated groups receive equal ranks
`[1,2,3,4]`	Checks already sorted input
`[4,3,2,1]`	Checks reverse sorted input
`[10^9,-10^9]`	Tests extreme constraint values

Edge Cases

Empty Array

An empty input array is a common source of bugs because some implementations assume at least one element exists. In this problem, an empty array should simply return another empty array.

The implementation handles this naturally because:

sorted(set([]))

produces an empty list, and iterating over the original array adds nothing to the result.

All Elements Are Equal

If every element is identical, all positions must receive rank 1.

A buggy implementation might accidentally assign increasing ranks to repeated values if duplicates are not removed before ranking.

Using a set guarantees only unique values are ranked. Since there is only one distinct value, it correctly receives rank 1, and every occurrence maps to that same rank.

Negative and Large Numbers

The constraints allow values from -10^9 to 10^9. Some incorrect solutions may assume only non-negative numbers or use array indexing based on values.

This implementation avoids that issue entirely because it uses sorting and hash maps rather than direct indexing by value. Python integers and Go integers both safely support the required range for this problem.