Abstract / Summary

Assign each number a rank based on its size relative to others in the array.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 71% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a single method arrayRankTransform. The method receives a list of integers and produces a sequence of rank values that correspond to the relative ordering of the distinct elements in the input. The smallest distinct value receives rank 1, the next smallest receives rank 2, and so on. The method yields each rank in the order of the original list, effectively transforming the input array into its rank representation.

Key Steps

Removing Duplicates and Sorting

unique = list(sorted(set(arr)))

The first operation converts the input list into a set, which eliminates duplicate entries. Converting the set back into a list after applying sorted produces an ordered collection of the distinct values. This step guarantees that each value appears exactly once and that the ordering reflects the natural numeric order.

Building the Rank Mapping

rank = {}
for i, u in enumerate(unique):
    rank[u] = i + 1

An empty dictionary rank is created to store the mapping from each distinct value to its rank. The enumerate function supplies a zero-based index i for each element u in the sorted unique list. Adding one to the index yields the 1-based rank required by the problem specification. The dictionary enables constant-time lookup of a rank given a value.

Producing the Result Sequence

for a in arr:
    yield rank[a]

The final loop iterates over the original input list arr. For each element a, the corresponding rank is retrieved from the rank dictionary and yielded. Using yield turns the method into a generator, allowing the caller to consume the transformed values lazily without constructing an intermediate list.

Edge Cases Handled

When the input list is empty, the set conversion yields an empty set, and the subsequent sorted call returns an empty list. The rank dictionary remains empty, and the final loop does not execute, resulting in an empty generator. This behavior correctly reflects that there are no elements to rank.

If all elements in the input are identical, the set reduces the collection to a single value. After sorting, unique contains one element, and the rank dictionary maps that value to rank 1. The generator then yields 1 for each occurrence in the original list, preserving the length of the input while assigning the same rank to every element.

The algorithm also accommodates negative numbers, zero, and large integer values because the sorting and dictionary operations rely on Python’s built-in comparison and hashing mechanisms, which handle the full range of integer values.

Performance Optimizations

The use of a set to eliminate duplicates is an O(n) operation that avoids the need for nested loops to detect repeated values. Sorting the deduplicated collection is performed on a list whose length equals the number of distinct elements, which is at most the length of the original array, thereby minimizing the amount of work required for ordering.

Storing ranks in a dictionary provides O(1) average-case lookup time when translating each original element to its rank. This eliminates the need for repeated linear searches through the sorted list.

Finally, yielding results instead of building a list reduces memory consumption, especially for large inputs. The generator produces each rank on demand, allowing the caller to process the output incrementally without allocating additional space for the entire transformed array.

Imagine having a big pile of mixed-up building blocks with numbers written on them. To figure out the order of these blocks, the first step is to take all the blocks and lay them out in a row from the smallest number to the largest one. While doing this, any extra blocks that have the same number are put away so that every number is unique.

Now, it is time to give each of these unique numbers a little badge to show its rank. The smallest number gets a badge that says one, the next smallest gets a badge that says two, and so on for all of them. These badges are kept in a special organized folder where you can look up any number to instantly see what its rank badge should be.

Finally, the code goes back through the original messy pile of blocks one by one. For every block, it checks the folder to find the right rank badge and points it out. This way, even though the blocks started in a jumble, every single one ends up with the correct label showing whether it is the smallest, the second smallest, or any other rank in the group.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java				TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python		JS	Java		Go	Rust	TS
	Progiez	C++	Python			Java
github	BigEggStudy			C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai					Java
	everthis				JS
	fsq	C++
	JoshCrozier				JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007		Python
	lzl124631x	C++
	Shamik07						Dart
	shreymehul			C#
	suxrobGM			C#
	varunu28					Java
	withaarzoo	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
lzl124631x	C++
Shamik07	Dart
shreymehul	C#
suxrobGM	C#
varunu28	Java
withaarzoo	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality