algoadvance

The problem is about assigning relative ranks to athletes based on their scores. You are given a list of integers representing the scores of athletes. Your task is to return a list of strings where each string describes the rank of the athlete. The ranks are assigned in descending order of the scores:

• The highest score gets the rank “Gold Medal”.
• The second highest score gets the rank “Silver Medal”.
• The third highest score gets the rank “Bronze Medal”.
• The rest of the scores get their respective ranks as the string representation of their rank numbers.

Clarifying Questions

1. What should be returned for empty input?
   • If the input list is empty, it’s not clearly specified, but typically returning an empty list would be appropriate.
2. Are there any constraints on scores?
   • The problem does not specify any constraints, but typically scores are non-negative integers.
3. Is the order of input scores preserved in the output?
   • Yes, the order of scores in the input list should be preserved in the output list of ranks.

Strategy

1. Sort Scores:
   • First, create a list of tuples where each tuple contains the score and its original index.
   • Sort this list by the scores in descending order to determine the medals and ranks.
2. Assign Ranks:
   • Traverse the sorted list and assign ranks based on the position:
     • For the first three elements, assign “Gold Medal”, “Silver Medal”, and “Bronze Medal”.
     • For the rest, assign the rank by converting the 1-based index to a string.
3. Construct Result:
   • Initialize a result list with the same length as the input list.
   • Populate this list with ranks according to the original indices of the scores.

Time Complexity

• Sorting the scores list will take (O(n \log n)) time.
• Assigning ranks and reconstructing the result list will take (O(n)) time.
• Therefore, the overall time complexity is (O(n \log n)), where (n) is the number of scores.

Code

Here’s the complete Python code for this problem:

def findRelativeRanks(score):
    # Prepare list of tuples (score, original_index)
    ranked_scores = [(s, i) for i, s in enumerate(score)]
    
    # Sort the list based on scores in descending order
    ranked_scores.sort(reverse=True, key=lambda x: x[0])
    
    # Initialize result list with empty strings
    result = [""] * len(score)
    
    # Assign ranks based on sorted order
    for rank, (s, i) in enumerate(ranked_scores):
        if rank == 0:
            result[i] = "Gold Medal"
        elif rank == 1:
            result[i] = "Silver Medal"
        elif rank == 2:
            result[i] = "Bronze Medal"
        else:
            result[i] = str(rank + 1)
    
    return result

# Example usage:
scores = [10, 3, 8, 9, 4]
print(findRelativeRanks(scores))
# Output: ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

This code effectively assigns the ranks and ensures the output retains the order of the original scores.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?