Rank Transform of an Array

Rank Transform of an Array

What is this problem about?

The Rank Transform of an Array problem asks you to replace each element with its rank (1 = smallest, ties get same rank, ranks are consecutive). This easy coding problem sorts the unique elements, assigns ranks, then replaces original array values. The array, hash table, and sorting interview pattern is demonstrated.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this as a clean implementation problem testing sorting with rank mapping. It's the 1D version of the harder matrix variant.

Algorithmic pattern used

Sort unique values + hash map rank assignment. Get sorted unique values. Build rank_map[value] = 1-indexed rank. For each element in original array, return rank_map[element].

Example explanation

arr=[40,10,20,30]. Sorted unique: [10,20,30,40]. Ranks: {10:1,20:2,30:3,40:4}. Result: [4,1,2,3].

arr=[100,100,100]: all same value. rank={100:1}. Result: [1,1,1].

Common mistakes candidates make

• Not handling duplicates (must give same rank to equal values).
• Using 0-indexed ranks (must be 1-indexed).
• Sorting the array directly instead of sorted unique values.
• Confusing rank with index.

Interview preparation tip

Rank Transform of an Array is a clean practice problem for "coordinate compression" — a technique used in many advanced problems to reduce large value ranges to small ranks. Practice coordinate compression: it appears in segment trees, BITs, and binary indexed queries where values can be huge but cardinality is small.