Relative Ranks: Sorting with Index Tracking

LeetCode Relative Ranks (problem 506) asks you to assign ranks to athletes based on their scores. The top three get medal names, and everyone else gets a numeric string. It is a clean exercise in the "sort indices by value" pattern that shows up across many problems.

The problem

You are given an integer array score of size n, where score[i] represents the score of the i-th athlete. All scores are unique. Return an array answer of size n where:

• answer[i] is "Gold Medal" if the athlete placed 1st
• answer[i] is "Silver Medal" if the athlete placed 2nd
• answer[i] is "Bronze Medal" if the athlete placed 3rd
• answer[i] is the placement number as a string for everyone else

Example: score = [10, 3, 8, 9, 4] produces ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"].

The athlete at index 0 has the highest score (10), so they get Gold. The athlete at index 3 has the second highest (9), so Silver. Index 2 has the third highest (8), so Bronze. Index 4 and index 1 get "4" and "5" respectively.

The approach

The key insight: you do not need to sort the scores themselves. You need to sort the indices by their corresponding scores. Once you have the indices in descending score order, position 0 in that sorted list is Gold, position 1 is Silver, position 2 is Bronze, and everything else gets its numeric rank.

The algorithm:

1. Create a list of indices [0, 1, 2, ..., n-1]
2. Sort these indices by score[i] in descending order
3. Walk through the sorted indices and assign ranks: the first gets "Gold Medal", the second "Silver Medal", the third "Bronze Medal", and the rest get their 1-indexed position as a string
4. Place each rank back at the original index in the result array

Step-by-step walkthrough

Using score = [10, 3, 8, 9, 4], let's trace through the full algorithm.

Observations:

• We never modify the original score array
• The sorted indices give us a direct mapping from rank position to original index
• Writing the result is a single pass over the sorted indices
• The top-3 medal logic is just a conditional on the loop counter

The code

def find_relative_ranks(score: list[int]) -> list[str]:
    n = len(score)
    indices = sorted(range(n), key=lambda i: score[i], reverse=True)

    result = [""] * n
    for rank, idx in enumerate(indices):
        if rank == 0:
            result[idx] = "Gold Medal"
        elif rank == 1:
            result[idx] = "Silver Medal"
        elif rank == 2:
            result[idx] = "Bronze Medal"
        else:
            result[idx] = str(rank + 1)

    return result

Line-by-line breakdown:

• indices = sorted(range(n), key=lambda i: score[i], reverse=True) creates a list of indices sorted by their score values from highest to lowest. For [10, 3, 8, 9, 4], this gives [0, 3, 2, 4, 1].
• result = [""] * n pre-allocates the output array with empty strings.
• for rank, idx in enumerate(indices) walks through the sorted indices. rank is the position (0, 1, 2, ...) and idx is the original index of that athlete.
• The if/elif/else block assigns the appropriate medal name for the top 3, or converts the 1-indexed rank to a string for everyone else.
• result[idx] = ... places the rank at the correct position in the output.

Complexity analysis

The sorting step is O(n log n). The rank assignment loop is O(n). Overall time is O(n log n). You could also use a max-heap to extract elements one by one, which is also O(n log n) but with worse constants in practice. The sorting approach is simpler and faster for this problem.

Building blocks

This problem demonstrates the sort-indices-then-rank pattern. Instead of sorting the data directly (which would lose positional information), you sort a separate list of indices using the original data as the sort key. This gives you a mapping from "rank position" to "original index" that you can use to write results back.

You will see this pattern in:

• Kth Largest Element (LeetCode 215): finding elements by rank after sorting or partial sorting
• Top K Frequent Elements (LeetCode 347): ranking elements by frequency, then returning the top ones
• Sort Colors (LeetCode 75): partitioning by category, which is a specialized rank assignment
• Queue Reconstruction by Height (LeetCode 406): sorting by one key to determine placement order

The core idea is always the same: sort to determine rank, then use that rank information to build your answer in the original index space.

Edge cases

• Single element: the array has one athlete, who always gets "Gold Medal"
• Two elements: only Gold and Silver get assigned, no Bronze
• Three elements: all three medals assigned, no numeric ranks
• Large scores: the values can be up to 10^6, but since we only compare them (not manipulate them), this does not affect the algorithm
• Already sorted (descending): produces ["Gold Medal", "Silver Medal", "Bronze Medal", "4", ...] in order, which is the simplest case

From understanding to recall

This is an easy problem with a clean pattern, but "easy" does not mean "instantly recallable under pressure." The sort-indices-by-value technique needs to be something you reach for automatically when you see a problem that asks you to rank or reorder elements while preserving original positions.

Spaced repetition helps you build that automatic recall. You solve this problem today, revisit it in two days, then a week later. Each time, the pattern locks in a little deeper. Eventually you do not think about how to sort indices by value. You just do it.

Related posts

• Sort Colors - Another ranking/partitioning problem where elements go to specific positions based on their value.
• Top K Frequent Elements - Uses frequency counting combined with ranking to find the most common elements.
• Kth Largest Element - Finding a specific rank position using sorting or quickselect.

The Relative Ranks problem is a gateway to understanding how sorting and index tracking work together. Once this pattern is second nature, you will recognize it instantly in harder problems where the ranking logic is buried under more complexity. Build that recognition through deliberate repetition.