Relative Ranks

Problem Statement

In this problem, you are provided with an integer array score where each element score[i] represents the score of the i-th athlete in a competition. The length of the array score is denoted as n. Each score within the array is unique, ensuring no ties between athletes. Athletes are ranked based on their scores, where the athlete with the highest score receives the highest rank, the second highest score gets the second rank, and so forth.

The ranking system translates scores into specific medals or placement numbers:

• The highest score is rewarded with the "Gold Medal."
• The second highest score receives the "Silver Medal."
• The third highest score is awarded the "Bronze Medal."
• From the fourth highest score onwards, the athletes' ranks are represented by their ordinal numbers, e.g., 4th, 5th, etc.

The final output is an array answer where answer[i] provides the rank or medal associated with the i-th athlete according to their score.

Examples

Example 1

Input:

score = [5,4,3,2,1]

Output:

["Gold Medal","Silver Medal","Bronze Medal","4","5"]

Explanation:

The placements are [1st, 2nd, 3rd, 4th, 5th].

Example 2

Input:

score = [10,3,8,9,4]

Output:

["Gold Medal","5","Bronze Medal","Silver Medal","4"]

Explanation:

The placements are [1st, 5th, 3rd, 2nd, 4th].

Constraints

• n == score.length
• 1 <= n <= 104
• 0 <= score[i] <= 106
• All the values in score are unique.

Approach and Intuition

To solve this ranking problem effectively, consider the following logical steps:

1. Sorting and Ranking:

   • Start by creating a reference to each score's original position because you need to return the rank in the order of the original scores.
   • Sort the scores in descending order so the highest scores come first. This approach helps directly in assigning the top three medals and subsequent numeric ranks.

2. Medal Assignment:

   • Iterate through the sorted list:
     • Assign "Gold Medal" to the highest score.
     • Assign "Silver Medal" to the second highest.
     • Assign "Bronze Medal" to the third highest.
     • For all other positions, convert the rank (1-based index of the sorted array) to a string and assign accordingly.

3. Reconstructing the Result:

   • Since sorting disrupts the order of elements, use the stored indices from the original array to place the ranks back in their corresponding positions.

Using this approach, you ensure efficiency and clarity in the formation of results, adhering to the unique conditions as stipulated by the rankings. This model effectively combines sorting, enumeration, and conditional logic to generate the desired outcome, which is both intuitive and straightforward under the constraints provided.

Solutions

class Solution {
private:
    int getMax(vector<int>& nums) {
        int highest = 0;
        for (int value : nums) {
            if (value > highest) {
                highest = value;
            }
        }
        return highest;
    }
public:
    vector<string> assignRanks(vector<int>& nums) {
        int total = nums.size();
    
        // Map each score with its index plus one to avoid confusion with zero indexing
        int highestValue = getMax(nums);
        vector<int> indexMap(highestValue + 1, 0);
        for (int i = 0; i < total; i++) {
            indexMap[nums[i]] = i + 1;
        }
    
        const vector<string> AWARDS = {"Gold Medal", "Silver Medal", "Bronze Medal"};
    
        // Sort and assign medals or ranks
        vector<string> results(total);
        int ranking = 1;
        for (int i = highestValue; i >= 0; i--) {
            if (indexMap[i] != 0) {
                int originalIdx = indexMap[i] - 1;
                if (ranking <= 3) {
                    results[originalIdx] = AWARDS[ranking - 1];
                } else {
                    results[originalIdx] = to_string(ranking);
                }
                ranking++;
            }
        }
        return results;
    }
};