LeetCode #506 Easy

Relative Ranks

Rank athletes by score and label the top three with medals, keeping output in the original order.

heapsortingarray

02

Intuition

💡

The trap is sorting the scores array directly and losing track of which athlete each score belonged to. The answer has to be written back into the ORIGINAL position of each athlete, so the original index has to travel with the score through the sort, not get discarded by it. Pack each score into a pair with its starting index before sorting, sort the pairs by score, then walk the sorted pairs and write the medal or rank string to answer[originalIndex]. The scores array itself is never reordered in place; only a parallel structure carrying both pieces of information is.

03

Approach

1

Pair every score with its original index

Build a list of (score, index) pairs in one pass over the input. This is the step that prevents the trap: once the score is bundled with where it came from, no later sort can lose that information.

2

Sort the pairs by score descending

Sort the pairs, not the raw scores, using score as the key. The pair carrying the highest score ends up first, and its original index is still attached.

3

Write results back by original index

Walk the sorted pairs in rank order, assigning 'Gold Medal', 'Silver Medal', 'Bronze Medal' to the first three and the numeric rank as a string to the rest, writing each result into answer[pair.index] rather than into the current loop position.

04

Solution & live demo

python

▶1class Solution:
▶2    def findRelativeRanks(self, score: List[int]) -> List[str]:
▶3        pairs = sorted(enumerate(score), key=lambda p: -p[1])
▶4        answer = [''] * len(score)
▶5        medals = ['Gold Medal', 'Silver Medal', 'Bronze Medal']
▶6        for rank, (orig_i, s) in enumerate(pairs):
▶7            answer[orig_i] = medals[rank] if rank < 3 else str(rank + 1)
▶8        return answer

05

Edge cases

single athlete

the lone score gets 'Gold Medal' regardless of its value

fewer than three athletes

only as many medal labels are assigned as there are athletes; no bronze if there are only two

scores already sorted descending

the sort is a no-op but pairing with indices still happens the same way

large gaps between scores

ranking depends only on relative order, not on the numeric gaps between scores

06

Complexity

Time

O(n log n)

Space

O(n)

dominated by sorting the (score, index) pairs; writing the answer back is O(n).