024. Rank Transform

Foundation · Download this solution · All solutions and shared helpers

Problem

Replace each integer by its one-based rank among the distinct values in the input. Equal values receive equal ranks and adjacent distinct ranks have no gaps. Return a new list in original position order; empty input returns [].

Examples

Example 1

rank_transform([40, 10, 20, 30])
=> [4, 1, 2, 3]

Ranks are returned in original order.

Example 2

rank_transform([5, 5, 1])
=> [2, 2, 1]

Duplicates share a rank.

Example 3

rank_transform([])
=> []

The rank map is empty.

Reveal the worked solution and reasoning

Why this mechanism works

The rank belongs to a value's position in the ordered set of distinct values, not to its original index. Build the complete rank map first, then project it back onto the original sequence. This separates ordering information from output order.

State and boundaries

rank maps each distinct value to its one-based position in sorted unique values.

Protocol

Deduplicate values with a set.
Sort the distinct values.
Assign ranks beginning at one.
Look up each original value's rank.

Visualization

distinct sorted: 10 20 30 40
ranks:            1  2  3  4
40 10 20 30 ->    4  1  2  3

Python implementation

def rank_transform(nums):
    rank = {value: i + 1 for i, value in enumerate(sorted(set(nums)))}
    return [rank[value] for value in nums]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

rank_transform([40, 10, 20, 30])

L2 rank_transform: rank = {value: i + 1 for i, value in enumerate(sorted(set(nums)))}
nums=[40, 10, 20, 30]; i=0; value=10

L2 rank_transform: rank = {value: i + 1 for i, value in enumerate(sorted(set(nums)))}
nums=[40, 10, 20, 30]; i=1; value=20

L2 rank_transform: rank = {value: i + 1 for i, value in enumerate(sorted(set(nums)))}
nums=[40, 10, 20, 30]; i=2; value=30

L2 rank_transform: rank = {value: i + 1 for i, value in enumerate(sorted(set(nums)))}
nums=[40, 10, 20, 30]; i=3; value=40

L2 rank_transform: rank = {value: i + 1 for i, value in enumerate(sorted(set(nums)))}
nums=[40, 10, 20, 30]; rank={10:1, 20:2, 30:3, 40:4}

L3 rank_transform: return [rank[value] for value in nums]
nums=[40, 10, 20, 30]; rank={10:1, 20:2, 30:3, 40:4}; value=40

L3 rank_transform: return [rank[value] for value in nums]
nums=[40, 10, 20, 30]; rank={10:1, 20:2, 30:3, 40:4}; value=10

L3 rank_transform: return [rank[value] for value in nums]
nums=[40, 10, 20, 30]; rank={10:1, 20:2, 30:3, 40:4}; value=20

L3 rank_transform: return [rank[value] for value in nums]
nums=[40, 10, 20, 30]; rank={10:1, 20:2, 30:3, 40:4}; value=30

L3 rank_transform: return [rank[value] for value in nums]
nums=[40, 10, 20, 30]; rank={10:1, 20:2, 30:3, 40:4}

Result: [4, 1, 2, 3]. Ranks are returned in original order.

rank_transform([5, 5, 1])

L2 rank_transform: rank = {value: i + 1 for i, value in enumerate(sorted(set(nums)))}
nums=[5, 5, 1]; i=0; value=1

L2 rank_transform: rank = {value: i + 1 for i, value in enumerate(sorted(set(nums)))}
nums=[5, 5, 1]; i=1; value=5

L2 rank_transform: rank = {value: i + 1 for i, value in enumerate(sorted(set(nums)))}
nums=[5, 5, 1]; rank={1:1, 5:2}

L3 rank_transform: return [rank[value] for value in nums]
nums=[5, 5, 1]; rank={1:1, 5:2}; value=5

L3 rank_transform: return [rank[value] for value in nums]
nums=[5, 5, 1]; rank={1:1, 5:2}; value=1

L3 rank_transform: return [rank[value] for value in nums]
nums=[5, 5, 1]; rank={1:1, 5:2}

Result: [2, 2, 1]. Duplicates share a rank.

Why the solution is correct

Sorted distinct values establish a strict total order, and enumeration assigns consecutive increasing ranks. Equal inputs share a dictionary key, so they receive equal ranks. Looking up the original sequence preserves its position order.

Time and space

O(n+u log u) expected time and O(n+u) space including output, where u is the distinct count.

Common mistakes

Ranking the fully sorted list gives gaps or inconsistent duplicate ranks. Returning the sorted ranks loses the original arrangement.

Reasoning card

State: rank maps each distinct value to its one-based position in sorted unique values.

Invariant: Rank mapping is complete before transformation.

Decision to rehearse: Sort unique values, then map back to original order.

Finish: Look up each original value's rank

Transfer exercise

Use coordinate compression to store large sparse coordinates in an array, while preserving the original distances separately.