LeetCode 506: Relative Ranks

Problem Restatement

We are given an integer array score.

score[i] is the score of the ith athlete.

All scores are unique.

Athletes are ranked from highest score to lowest score:

We need to return an array answer where:

answer[i]

is the rank of the ith athlete in the original input order.

The official problem states that all scores are unique and asks us to return each athlete’s rank based on descending score order.

Input and Output

Function shape:

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        ...

Examples

Example 1:

score = [5, 4, 3, 2, 1]

The scores are already in descending order.

So the placements are:

The answer is:

["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Example 2:

score = [10, 3, 8, 9, 4]

Sort scores from highest to lowest:

10, 9, 8, 4, 3

So:

Put ranks back into original index order:

["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

First Thought: Sort the Scores

The ranking comes from sorting scores in descending order.

However, if we sort only the values, we lose the original athlete positions.

For example:

score = [10, 3, 8, 9, 4]

After sorting:

[10, 9, 8, 4, 3]

we know the rank order, but we still need to place each rank back into the answer array using the original index.

So we need to remember where each score came from.

Key Insight

Sort the indices instead of sorting only the scores.

Create:

indices = [0, 1, 2, ..., n - 1]

Then sort those indices by their corresponding scores:

indices.sort(key=lambda i: score[i], reverse=True)

After sorting:

indices[0]

is the original index of the highest-scoring athlete.

indices[1]

is the original index of the second-highest-scoring athlete.

Then we can assign ranks directly into the correct answer positions.

Algorithm

Let n = len(score).

Create an answer array:

answer = [""] * n

Create indices:

indices = list(range(n))

Sort them by descending score.

Then scan the sorted indices.

For position place_index and original index athlete_index:

1. If place_index == 0, assign "Gold Medal".
2. If place_index == 1, assign "Silver Medal".
3. If place_index == 2, assign "Bronze Medal".
4. Otherwise, assign str(place_index + 1).

The + 1 is needed because array positions are zero-based, but ranks start at 1.

Correctness

Sorting the indices by score[i] in descending order places the athletes from highest score to lowest score.

Because all scores are unique, every athlete has a distinct placement.

For every sorted position place_index, the athlete at indices[place_index] has placement place_index + 1.

The algorithm assigns the correct medal string for placements 1, 2, and 3.

For every placement from 4 onward, it assigns the placement number as a string.

Each rank is written to answer[athlete_index], so the final array preserves the original athlete order.

Therefore, answer[i] is exactly the rank of the ith athlete.

Complexity

Implementation

from typing import List

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        n = len(score)
        answer = [""] * n

        indices = list(range(n))
        indices.sort(key=lambda i: score[i], reverse=True)

        medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]

        for place_index, athlete_index in enumerate(indices):
            if place_index < 3:
                answer[athlete_index] = medals[place_index]
            else:
                answer[athlete_index] = str(place_index + 1)

        return answer

Code Explanation

Create the result array:

answer = [""] * n

This will store ranks in the original athlete order.

Create the list of original indices:

indices = list(range(n))

Sort indices by score descending:

indices.sort(key=lambda i: score[i], reverse=True)

The medal names are stored in order:

medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]

Now each position in indices tells us a placement:

for place_index, athlete_index in enumerate(indices):

If the athlete is in the top three, assign the medal:

answer[athlete_index] = medals[place_index]

Otherwise, assign the numeric rank:

answer[athlete_index] = str(place_index + 1)

Finally, return the answer.

Testing

def test_find_relative_ranks():
    s = Solution()

    assert s.findRelativeRanks([5, 4, 3, 2, 1]) == [
        "Gold Medal",
        "Silver Medal",
        "Bronze Medal",
        "4",
        "5",
    ]

    assert s.findRelativeRanks([10, 3, 8, 9, 4]) == [
        "Gold Medal",
        "5",
        "Bronze Medal",
        "Silver Medal",
        "4",
    ]

    assert s.findRelativeRanks([1]) == ["Gold Medal"]

    assert s.findRelativeRanks([2, 1]) == [
        "Gold Medal",
        "Silver Medal",
    ]

    assert s.findRelativeRanks([1, 100, 50]) == [
        "Bronze Medal",
        "Gold Medal",
        "Silver Medal",
    ]

    print("all tests passed")

Test meaning: