We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Relative Ranks

Number: 506

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Adobe

Problem Description

Given an array of unique scores for athletes, determine each athlete's rank based on their score. The highest score gets "Gold Medal", the second-highest "Silver Medal", the third-highest "Bronze Medal", and the rest receive their numerical placement as a string.

Key Insights

  • We need to maintain the original indices while sorting the scores.
  • Sorting the score array in descending order helps determine each athlete's placement.
  • Special handling for the top three placements with medal names.
  • Use an additional array to store the final ranking based on original indices.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting of the scores. Space Complexity: O(n) for storing indexed scores and the result array.

Solution

The approach is to pair each score with its original index and then sort the list in descending order based on scores. Once sorted, iterate through the list to assign appropriate ranks:

  • For the first, second, and third positions, assign "Gold Medal", "Silver Medal", and "Bronze Medal" respectively.
  • For all other positions, assign the string value of the current placement index (1-indexed). Finally, place the assigned rank into the result array at the correct original index.

Code Solutions

# Define the function to assign relative ranks
def findRelativeRanks(score):
    # Pair each score with its original index
    score_with_index = [(s, i) for i, s in enumerate(score)]
    # Sort the list descending by score
    score_with_index.sort(key=lambda x: x[0], reverse=True)
    
    n = len(score)
    answer = [""] * n  # Initialize the answer list with empty strings
    
    for rank, (s, i) in enumerate(score_with_index):
        # Determine the medal or numerical rank
        if rank == 0:
            answer[i] = "Gold Medal"
        elif rank == 1:
            answer[i] = "Silver Medal"
        elif rank == 2:
            answer[i] = "Bronze Medal"
        else:
            answer[i] = str(rank + 1)  # rank is zero-based; adjust for 1-indexed result
    return answer

# Example Execution
print(findRelativeRanks([10,3,8,9,4]))
← Back to All Questions