Problem Description

You are given an array score where score[i] represents the score of the i-th athlete in a competition. All scores are unique.

Your task is to assign ranks to each athlete based on their scores, following these rules:

• Athletes are ranked from highest score to lowest score
• The athlete with the highest score gets "Gold Medal"
• The athlete with the second highest score gets "Silver Medal"
• The athlete with the third highest score gets "Bronze Medal"
• Athletes in 4th place and beyond get their numerical placement as a string (e.g., "4", "5", "6", etc.)

You need to return an array answer where answer[i] is the rank of the i-th athlete in the original score array.

For example, if score = [5, 4, 3, 2, 1], then:

• Athlete at index 0 (score 5) has the highest score → "Gold Medal"
• Athlete at index 1 (score 4) has the second highest score → "Silver Medal"
• Athlete at index 2 (score 3) has the third highest score → "Bronze Medal"
• Athlete at index 3 (score 2) has the fourth highest score → "4"
• Athlete at index 4 (score 1) has the fifth highest score → "5"

So the output would be ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"].

The solution works by creating an index array and sorting it based on the scores in descending order. Then it assigns the appropriate rank strings to each athlete based on their sorted position.

Intuition

The key insight is that we need to maintain the relationship between each athlete's original position in the array and their rank based on their score. Simply sorting the scores would lose track of which athlete had which score.

Think of it this way: if we directly sort the scores, we know the ranking order, but we don't know which athlete (index) each score belongs to. We need a way to remember "this score came from athlete at index i."

This leads us to the idea of sorting indices instead of scores. We create an index array [0, 1, 2, ..., n-1] and sort these indices based on the scores they point to. When we sort idx by score[idx] in descending order, idx[0] will contain the index of the athlete with the highest score, idx[1] will contain the index of the athlete with the second highest score, and so on.

Now we can traverse this sorted index array. The position in the sorted array tells us the rank (0th position = 1st place, 1st position = 2nd place, etc.), and the value at that position tells us which athlete (original index) should receive that rank.

For the first three positions (indices 0, 1, 2 in the sorted array), we assign the special medal strings. For positions 3 and beyond, we assign the numerical rank as a string. Since array indices start at 0 but ranks start at 1, we use i + 1 to get the actual rank number.

This approach elegantly solves the problem in O(n log n) time due to sorting, while maintaining the mapping between original positions and final ranks.

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

The solution uses sorting with index tracking to assign ranks while preserving the original positions of athletes.

Step 1: Create an index array

idx = list(range(n))

We create an array idx = [0, 1, 2, ..., n-1] to keep track of the original indices of athletes.

Step 2: Sort indices by scores in descending order

idx.sort(key=lambda x: -score[x])

Instead of sorting the scores directly, we sort the indices based on their corresponding scores. The key=lambda x: -score[x] ensures descending order (negative sign reverses the order). After sorting:

• idx[0] contains the index of the athlete with the highest score
• idx[1] contains the index of the athlete with the second highest score
• And so on...

Step 3: Define medal names

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

We prepare the special rank strings for the top 3 athletes.

Step 4: Assign ranks to original positions

ans = [None] * n
for i, j in enumerate(idx):
    ans[j] = top3[i] if i < 3 else str(i + 1)

We iterate through the sorted indices:

• i represents the current rank position (0-indexed)
• j represents the original index of the athlete at this rank
• If i < 3, we assign the corresponding medal from top3[i]
• Otherwise, we assign the numerical rank as a string: str(i + 1) (adding 1 because ranks start from 1, not 0)

The key insight is that ans[j] places the rank at the correct original position. For example, if the athlete at original index 2 has the highest score, then after sorting, idx[0] = 2, and we set ans[2] = "Gold Medal".

Time Complexity: O(n log n) due to sorting
Space Complexity: O(n) for the index array and answer array

Example Walkthrough

Let's walk through a small example with score = [10, 3, 8, 9, 4].

Step 1: Create index array

• idx = [0, 1, 2, 3, 4] (representing the original positions)

Step 2: Sort indices by scores (descending)

• We need to sort idx based on the scores they point to:
  • Index 0 → score 10 (highest)
  • Index 3 → score 9 (second highest)
  • Index 2 → score 8 (third highest)
  • Index 4 → score 4 (fourth highest)
  • Index 1 → score 3 (lowest)
• After sorting: idx = [0, 3, 2, 4, 1]

Step 3: Assign ranks

• Initialize: ans = [None, None, None, None, None]
• Iterate through sorted indices:
  • i=0, j=0: Athlete at original index 0 gets rank 1 → ans[0] = "Gold Medal"
  • i=1, j=3: Athlete at original index 3 gets rank 2 → ans[3] = "Silver Medal"
  • i=2, j=2: Athlete at original index 2 gets rank 3 → ans[2] = "Bronze Medal"
  • i=3, j=4: Athlete at original index 4 gets rank 4 → ans[4] = "4"
  • i=4, j=1: Athlete at original index 1 gets rank 5 → ans[1] = "5"

Final Result: ans = ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

This correctly maps each athlete's original position to their rank based on their score.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The dominant operation in this algorithm is the sorting step idx.sort(key=lambda x: -score[x]), which sorts the indices based on their corresponding scores in descending order. Sorting n elements takes O(n × log n) time. The other operations include:

• Creating the index list idx = list(range(n)): O(n)
• Iterating through the sorted indices to assign ranks: O(n)

Since O(n × log n) dominates O(n), the overall time complexity is O(n × log n).

Space Complexity: O(n)

The algorithm uses additional space for:

• The idx list containing n indices: O(n)
• The ans list for storing the final rankings: O(n)
• The top3 list containing 3 constant strings: O(1)

The total auxiliary space used is O(n) + O(n) + O(1) = O(n), where n is the length of the array score.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Directly Sorting the Original Array

A common mistake is sorting the score array directly, which loses the original position information needed to place ranks in the correct output positions.

Incorrect Approach:

# This loses original position information!
score.sort(reverse=True)
result = []
for i, s in enumerate(score):
    if i < 3:
        result.append(medals[i])
    else:
        result.append(str(i + 1))
# Now we don't know where to place these ranks!

Solution: Always use index-based sorting to maintain the mapping between original positions and sorted positions.

2. Off-by-One Error in Rank Assignment

Forgetting that rank positions are 1-indexed while array indices are 0-indexed can lead to incorrect rank numbers.

Incorrect:

# Wrong: Athletes ranked 4th and beyond get "3", "4", "5"...
result[athlete_index] = str(rank)  # Should be rank + 1

Correct:

result[athlete_index] = str(rank + 1)  # Converts 0-indexed rank to 1-indexed

3. Using Wrong Comparison for Descending Sort

When sorting with a lambda function, forgetting to negate the score or using the wrong comparison leads to ascending order instead of descending.

Incorrect:

# This sorts in ascending order (lowest score first)
indices.sort(key=lambda x: score[x])

Correct:

# Use negative to get descending order
indices.sort(key=lambda x: -score[x])
# Or use reverse parameter
indices.sort(key=lambda x: score[x], reverse=True)

4. Creating Score-Index Pairs Incorrectly

Some solutions create pairs of (score, index) but mix up the order or sorting direction.

Incorrect:

# Creating pairs but sorting by index instead of score
pairs = [(i, score[i]) for i in range(n)]
pairs.sort()  # This sorts by index first, not score!

Correct:

# Put score first for natural sorting, or specify key
pairs = [(score[i], i) for i in range(n)]
pairs.sort(reverse=True)  # Now sorts by score correctly

5. Assuming Scores Can Be Tied

The problem states all scores are unique, but implementing tie-breaking logic adds unnecessary complexity and can introduce bugs.

Overcomplicated:

# Unnecessary handling of ties
if i < 3 and (i == n-1 or score[idx[i]] != score[idx[i+1]]):
    result[idx[i]] = medals[i]

Simple and Correct:

# Since scores are unique, no tie-breaking needed
if i < 3:
    result[idx[i]] = medals[i]