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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Relative Ranks

Difficulty: Easy

Problem Description

You are given an integer array score of size n, where score[i] is the score of the i<sup>th</sup> athlete in a competition. All the scores are guaranteed to be unique. The athletes are placed based on their scores, where the 1<sup>st</sup> place athlete has the highest score, the 2<sup>nd</sup> place athlete has the 2<sup>nd</sup> highest score, and so on. The placement of each athlete determines their rank:

  • The 1<sup>st</sup> place athlete's rank is "Gold Medal".
  • The 2<sup>nd</sup> place athlete's rank is "Silver Medal".
  • The 3<sup>rd</sup> place athlete's rank is "Bronze Medal".
  • For the 4<sup>th</sup> place to the n<sup>th</sup> place athlete, their rank is their placement number (i.e., the x<sup>th</sup> place athlete's rank is "x").

Return an array answer of size n where answer[i] is the rank of the i<sup>th</sup> athlete.

Key Insights

  • The scores are unique, allowing for a direct mapping between scores and ranks.
  • Sorting the scores can help in determining the rank placements easily.
  • The use of a hashmap can facilitate quick lookups for the original indices while assigning ranks.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting of the scores. Space Complexity: O(n) for storing the results and auxiliary data structures.

Solution

To solve the problem, we can follow these steps:

  1. Create a list of tuples where each tuple contains a score and its original index.
  2. Sort this list based on the scores in descending order.
  3. Iterate through the sorted list and assign ranks based on the index in the sorted list: "Gold Medal" for the first, "Silver Medal" for the second, "Bronze Medal" for the third, and the respective rank number for the rest.
  4. Use the original indices to place the ranks back in the result array.

Code Solutions

def findRelativeRanks(score):
    # Create a list of tuples (score, index)
    indexed_scores = [(s, i) for i, s in enumerate(score)]
    # Sort the list by score in descending order
    indexed_scores.sort(key=lambda x: x[0], reverse=True)
    
    # Initialize the answer array
    answer = [""] * len(score)
    
    # Assign ranks based on sorted order
    for rank, (s, i) in enumerate(indexed_scores):
        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)
    
    return answer
← Back to All Questions