Difficulty: 🟢 Easy
Topics: Array, Sorting, Heap (Priority Queue)

Solution

LeetCode 506 - Relative Ranks

Problem Understanding

The problem gives us an array named score, where each element represents the score earned by an athlete in a competition. Every athlete has a unique score, which means there are no ties to worry about when determining rankings.

We need to determine each athlete's placement based on score order. The athlete with the highest score receives first place, the athlete with the second highest score receives second place, and so on.

The output must preserve the original order of athletes. This is an important detail. We are not simply returning the rankings in sorted order. Instead, for every original index i, we must place that athlete's rank string into answer[i].

The top three athletes receive special labels:

First place gets "Gold Medal"
Second place gets "Silver Medal"
Third place gets "Bronze Medal"

Every athlete after third place receives their numeric placement as a string, such as "4" or "5".

The constraints are relatively small:

1 <= n <= 10^4
Scores are unique
Scores can be as large as 10^6

Since n is at most 10^4, an O(n log n) sorting solution is perfectly acceptable. A quadratic O(n^2) approach may still pass for some inputs, but it is inefficient and unnecessary when sorting provides a cleaner and faster solution.

Several edge cases are important:

A single athlete should receive "Gold Medal"
Exactly two or three athletes should correctly receive only the applicable medals
Scores may already be sorted ascending or descending
Very large score values do not matter because only relative ordering is important
Since scores are guaranteed unique, we never need tie handling logic

Approaches

Brute Force Approach

A straightforward approach is to determine each athlete's rank independently.

For every athlete, we compare their score against every other athlete's score and count how many athletes have a higher score. If exactly zero athletes have a higher score, that athlete is first place. If one athlete has a higher score, that athlete is second place, and so on.

After determining the placement number, we convert the top three placements into medal strings and use numeric strings for the remaining placements.

This approach works because counting how many scores exceed the current score directly determines the rank.

However, this method requires nested loops. For every athlete, we scan the entire array again. That leads to O(n^2) time complexity, which is unnecessary when sorting can solve the problem more efficiently.

Optimal Approach

The key observation is that rankings are entirely determined by score ordering.

If we sort the athletes by score in descending order, then:

Index 0 in the sorted list is first place
Index 1 is second place
Index 2 is third place
Index i corresponds to placement i + 1

To preserve original ordering, we store both the score and its original index before sorting. After sorting, we assign the correct rank string and place it into the result array at the athlete's original index.

Sorting reduces the problem from repeated comparisons to a single ordering operation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) or O(n)	Compare every athlete against every other athlete
Optimal	O(n log n)	O(n)	Sort athletes by score and assign ranks efficiently

Algorithm Walkthrough

Create a list of pairs containing each athlete's score and original index.

We need the original index because the final answer must match the input order. A pair like (score, index) allows us to sort by score while still knowing where the athlete belongs in the result array. 2. Sort the pairs in descending order by score.

After sorting:

The first athlete in the sorted list has the highest score
The second athlete has the second highest score
And so on

This directly gives us placement order. 3. Create a result array of size n.

This array will store the final rank strings. 4. Traverse the sorted list.

For each athlete in sorted order:

Rank 0 gets "Gold Medal"
Rank 1 gets "Silver Medal"
Rank 2 gets "Bronze Medal"
Any other rank gets the string version of rank + 1

Place the rank string into the athlete's original index in the result array.

This restores the original ordering required by the problem. 6. Return the result array.

Why it works

Sorting the athletes by descending score guarantees that their positions in the sorted list exactly match their competition placements. Since all scores are unique, there is a one to one mapping between sorted position and rank. By storing original indices, we can assign rankings while still reconstructing the answer in the original input order.

Python Solution

from typing import List

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

        # Store score along with original index
        athletes = [(score_value, index) for index, score_value in enumerate(score)]

        # Sort by score in descending order
        athletes.sort(reverse=True)

        result = [""] * n

        for rank, (_, original_index) in enumerate(athletes):
            if rank == 0:
                result[original_index] = "Gold Medal"
            elif rank == 1:
                result[original_index] = "Silver Medal"
            elif rank == 2:
                result[original_index] = "Bronze Medal"
            else:
                result[original_index] = str(rank + 1)

        return result

The implementation begins by pairing every score with its original index using enumerate. This is necessary because sorting changes the order of athletes, but the final answer must preserve the original order.

The list is then sorted in descending order. Since tuples compare by their first element by default, the scores determine ordering automatically.

A result array is initialized with empty strings. As we iterate through the sorted athletes, the loop index represents the athlete's placement:

0 means first place
1 means second place
2 means third place

We assign the appropriate medal string for the top three positions. For all remaining positions, we convert the placement number into a string.

Finally, we store the rank string at the athlete's original index and return the completed result array.

Go Solution

package main

import (
	"sort"
	"strconv"
)

func findRelativeRanks(score []int) []string {
	n := len(score)

	type Athlete struct {
		score int
		index int
	}

	athletes := make([]Athlete, n)

	for i, s := range score {
		athletes[i] = Athlete{
			score: s,
			index: i,
		}
	}

	sort.Slice(athletes, func(i, j int) bool {
		return athletes[i].score > athletes[j].score
	})

	result := make([]string, n)

	for rank, athlete := range athletes {
		if rank == 0 {
			result[athlete.index] = "Gold Medal"
		} else if rank == 1 {
			result[athlete.index] = "Silver Medal"
		} else if rank == 2 {
			result[athlete.index] = "Bronze Medal"
		} else {
			result[athlete.index] = strconv.Itoa(rank + 1)
		}
	}

	return result
}

The Go solution follows the same logic as the Python implementation, but uses a custom Athlete struct to store both the score and original index.

Go does not provide built in tuple support like Python, so a struct makes the code clearer and more maintainable.

Sorting is performed with sort.Slice, using a custom comparison function for descending order.

Numeric placements are converted into strings using strconv.Itoa.

Since slices in Go are dynamically sized views over arrays, the result slice is initialized with length n before assignments begin.

Worked Examples

Example 1

Input:

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

Step 1: Pair scores with indices

Score	Original Index
5	0
4	1
3	2
2	3
1	4

Step 2: Sort descending

The array is already sorted:

Rank Position	Score	Original Index
0	5	0
1	4	1
2	3	2
3	2	3
4	1	4

Step 3: Assign ranks

Rank Position	Assigned Rank	Original Index	Result State
0	Gold Medal	0	["Gold Medal", "", "", "", ""]
1	Silver Medal	1	["Gold Medal", "Silver Medal", "", "", ""]
2	Bronze Medal	2	["Gold Medal", "Silver Medal", "Bronze Medal", "", ""]
3	4	3	["Gold Medal", "Silver Medal", "Bronze Medal", "4", ""]
4	5	4	["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Final output:

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

Example 2

Input:

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

Step 1: Pair scores with indices

Score	Original Index
10	0
3	1
8	2
9	3
4	4

Step 2: Sort descending

Rank Position	Score	Original Index
0	10	0
1	9	3
2	8	2
3	4	4
4	3	1

Step 3: Assign ranks

Rank Position	Assigned Rank	Original Index	Result State
0	Gold Medal	0	["Gold Medal", "", "", "", ""]
1	Silver Medal	3	["Gold Medal", "", "", "Silver Medal", ""]
2	Bronze Medal	2	["Gold Medal", "", "Bronze Medal", "Silver Medal", ""]
3	4	4	["Gold Medal", "", "Bronze Medal", "Silver Medal", "4"]
4	5	1	["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

Final output:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Extra storage for paired athletes and result array

The sorting step is the most expensive operation, requiring O(n log n) time. All remaining operations are linear scans over the array.

The algorithm also uses additional memory for the athlete pairs and the output array, leading to O(n) auxiliary space usage.

Test Cases

from typing import List

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

        athletes = [(value, index) for index, value in enumerate(score)]
        athletes.sort(reverse=True)

        result = [""] * n

        for rank, (_, original_index) in enumerate(athletes):
            if rank == 0:
                result[original_index] = "Gold Medal"
            elif rank == 1:
                result[original_index] = "Silver Medal"
            elif rank == 2:
                result[original_index] = "Bronze Medal"
            else:
                result[original_index] = str(rank + 1)

        return result

solution = Solution()

# Provided example 1
assert solution.findRelativeRanks([5,4,3,2,1]) == [
    "Gold Medal",
    "Silver Medal",
    "Bronze Medal",
    "4",
    "5"
]

# Provided example 2
assert solution.findRelativeRanks([10,3,8,9,4]) == [
    "Gold Medal",
    "5",
    "Bronze Medal",
    "Silver Medal",
    "4"
]

# Single athlete
assert solution.findRelativeRanks([100]) == [
    "Gold Medal"
]

# Two athletes
assert solution.findRelativeRanks([20,10]) == [
    "Gold Medal",
    "Silver Medal"
]

# Three athletes
assert solution.findRelativeRanks([30,20,10]) == [
    "Gold Medal",
    "Silver Medal",
    "Bronze Medal"
]

# Ascending scores
assert solution.findRelativeRanks([1,2,3,4]) == [
    "4",
    "Bronze Medal",
    "Silver Medal",
    "Gold Medal"
]

# Random ordering
assert solution.findRelativeRanks([50,80,70,60]) == [
    "4",
    "Gold Medal",
    "Silver Medal",
    "Bronze Medal"
]

# Large values
assert solution.findRelativeRanks([1000000,999999,1]) == [
    "Gold Medal",
    "Silver Medal",
    "Bronze Medal"
]

# Four athletes
assert solution.findRelativeRanks([40,10,30,20]) == [
    "Gold Medal",
    "4",
    "Silver Medal",
    "Bronze Medal"
]

Test	Why
`[5,4,3,2,1]`	Validates standard descending ordering
`[10,3,8,9,4]`	Validates mixed ordering and index restoration
`[100]`	Tests smallest possible input
`[20,10]`	Tests handling with only two medals
`[30,20,10]`	Tests exactly three medal assignments
`[1,2,3,4]`	Tests ascending input order
`[50,80,70,60]`	Tests arbitrary ordering
`[1000000,999999,1]`	Tests large score values
`[40,10,30,20]`	Tests transition from medals to numeric ranks

Edge Cases

One important edge case is when the input contains only a single athlete. In this situation, that athlete must receive "Gold Medal". A careless implementation might assume at least three athletes exist and incorrectly attempt to assign silver or bronze medals. The current implementation handles this naturally because the sorted loop assigns the first athlete rank 0, which maps directly to "Gold Medal".

Another important case occurs when there are exactly two or three athletes. The algorithm must correctly assign only the medals that actually apply. For example, with two athletes, there should be no bronze medal assignment. Since the implementation checks ranks sequentially using explicit conditions, only existing athletes receive medals.

Ascending order input is also a common source of mistakes. For example, [1,2,3,4] places the highest score at the end of the original array. If an implementation forgets to preserve original indices before sorting, the output order becomes incorrect. By storing (score, original_index) pairs, the algorithm correctly reconstructs the answer in original input order.

A final subtle edge case involves very large score values. Since rankings depend only on relative ordering, not arithmetic operations, large numbers do not create overflow or precision issues. The algorithm simply sorts and compares values directly.