Rank Transform of an Array: Sort and Map

Given an array of integers, replace each element with its rank. The rank is assigned based on how large the element is: the smallest element gets rank 1, the next smallest gets rank 2, and so on. If two elements are equal, they receive the same rank, and the next rank is not skipped.

This is LeetCode 1331: Rank Transform of an Array.

Why this problem matters

Rank transform is a fundamental operation that appears across many domains. In statistics, ranking data points is a standard preprocessing step. In competitive programming, coordinate compression (which is essentially rank transform) lets you map large value ranges into compact indices. Understanding this pattern gives you a reusable tool for any problem where relative order matters more than absolute values.

The problem also tests your ability to combine two core operations, sorting and hash map lookup, into a clean pipeline. You sort to determine the ordering, build a lookup table, and then map the original array through that table. Each step is simple on its own, but chaining them together is where the real skill lies.

This kind of "precompute a mapping, then apply it" approach shows up in problems far harder than this one. Getting comfortable with it here means you will recognize it faster when the stakes are higher.

The key insight

You do not need to compare every pair of elements to figure out rankings. Instead, sort the unique values. The position of each value in that sorted list is its rank. Once you have built a hash map from value to rank, you can transform the entire original array in a single pass.

The key word is "unique." If duplicates exist, they all share the same rank. By extracting unique values first and sorting those, you automatically handle ties without any special logic.

The solution

def arrayRankTransform(arr):
    sorted_unique = sorted(set(arr))
    rank_map = {val: rank for rank, val in enumerate(sorted_unique, 1)}
    return [rank_map[val] for val in arr]

Here is what each line does:

• sorted(set(arr)) extracts the unique values from the array and sorts them in ascending order. Using a set removes duplicates, and sorted returns a new list in order.
• The dictionary comprehension {val: rank for rank, val in enumerate(sorted_unique, 1)} pairs each unique value with its rank. The enumerate starts at 1, so the smallest value maps to rank 1, the next to rank 2, and so on.
• The final list comprehension [rank_map[val] for val in arr] walks through the original array and replaces each value with its rank from the map. Since the map was built from unique sorted values, duplicates naturally get the same rank.

Visual walkthrough

The process is always the same: sort unique values, number them starting from 1, and look up each original element in the resulting map. No matter how large the array or how many duplicates it contains, this three-step pipeline produces the correct ranks.

Complexity analysis

The time complexity is dominated by the sort. Building the set is O(n), sorting the unique values is O(n log n) in the worst case (when all values are distinct), building the hash map is O(n), and the final mapping pass is O(n). Everything except the sort is linear, so the overall time is O(n log n).

Space is O(n) for the set, the sorted list, the hash map, and the result array. Each of these is at most n elements, so total auxiliary space is O(n).

The building blocks

1. Sorting as a ranking tool

Sorting naturally reveals the rank of each element. The smallest value ends up at index 0, the next at index 1, and so on. Whenever a problem asks about relative position or ordering, sorting is usually the first step. This same idea powers problems like Height Checker, Relative Ranks, and many coordinate compression tasks.

2. Hash map for O(1) lookup

After sorting, you need a fast way to look up the rank of any value. A hash map gives you O(1) lookups, which means the final pass through the original array stays linear. Without the map, you would need binary search (O(log n) per lookup) or worse. The combination of "sort once, build a map, query many times" is a pattern you will see again and again.

Edge cases

• Empty array: return an empty array. There are no elements to rank.
• Single element: the only value gets rank 1.
• All identical values: every element maps to rank 1, since there is only one unique value.
• Already sorted: the result is [1, 2, 3, ..., n] (assuming all values are distinct).
• Negative numbers: negative values sort before positive ones, but the logic is identical. The smallest value still gets rank 1 regardless of sign.

From understanding to recall

This problem is easy to understand once you see the sort-and-map approach. But understanding is not the same as being able to produce the solution quickly under time pressure. In an interview, you want the pattern to be automatic: see "replace with rank," immediately think "sort unique values, build a map, apply it."

Spaced repetition helps you cross that gap. Solve this problem today, revisit it in a few days, then again next week. Each pass makes the sort-and-map pipeline feel more natural. The goal is not to memorize three lines of Python. The goal is to internalize the general pattern so it transfers to harder problems like coordinate compression, relative sort, and offline query processing.

Related posts

• Sort an Array - Sorting fundamentals that power the ranking step
• Relative Sort Array - Custom ordering based on a reference array
• Height Checker - Rank comparison using sort and compare

Rank Transform of an Array is a clean example of the "precompute and map" strategy. You invest a small amount of upfront work (sorting and building a hash map) so that the final transformation is fast and simple. That tradeoff, doing a bit more work up front to make the main pass trivial, is one of the most useful ideas in algorithm design. Build familiarity with it here, and you will reach for it naturally when harder problems demand it.