Replace Elements by Their Rank

Easy

Sort the distinct values, then map back

Problem

Replace each array element by its rank (1 = smallest) among the distinct values.

In simple words

Sort the distinct values to learn each one's rank, then map every element to its rank.

The idea

Collect the distinct values, sort them, and build a map from value to its 1-based position. A second pass over the original array replaces each element with its rank in O(n log n) total.

The trick

Deduplicate before ranking, or equal values would get different ranks.
This is coordinate compression, used everywhere in Fenwick and segment tree problems.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(n log n)spaceO(n)

1rank = map from value to position in sorted distinct list2for x: output rank[x]

Input

array: [20, 15, 26, 2, 98, 6]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [20, 15, 26, 2, 98, 6]
Output:: [4, 3, 5, 1, 6, 2]
Explanation:: Smallest gets rank 1, next rank 2, and so on.

Example 2

Input:: nums = [2, 2, 1]
Output:: [2, 2, 1]
Explanation:: Equal values share a rank.

Example 3

Input:: nums = [10, 20, 30]
Output:: [1, 2, 3]
Explanation:: Already ordered → 1,2,3.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.