Code Implementation

class Solution:
    def findRelativeRanks(self, score):
        # Pair each score with its index
        indexed = list(enumerate(score))
        # Sort by score in descending order
        indexed.sort(key=lambda x: -x[1])
        result = [""] * len(score)
        for rank, (idx, sc) in enumerate(indexed):
            if rank == 0:
                result[idx] = "Gold Medal"
            elif rank == 1:
                result[idx] = "Silver Medal"
            elif rank == 2:
                result[idx] = "Bronze Medal"
            else:
                result[idx] = str(rank + 1)
        return result
      

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        int n = score.size();
        vector<pair<int, int>> indexed;
        for (int i = 0; i < n; ++i) {
            indexed.push_back({score[i], i});
        }
        sort(indexed.rbegin(), indexed.rend());
        vector<string> result(n);
        for (int rank = 0; rank < n; ++rank) {
            int idx = indexed[rank].second;
            if (rank == 0)
                result[idx] = "Gold Medal";
            else if (rank == 1)
                result[idx] = "Silver Medal";
            else if (rank == 2)
                result[idx] = "Bronze Medal";
            else
                result[idx] = to_string(rank + 1);
        }
        return result;
    }
};
      

class Solution {
    public String[] findRelativeRanks(int[] score) {
        int n = score.length;
        int[][] indexed = new int[n][2];
        for (int i = 0; i < n; i++) {
            indexed[i][0] = score[i];
            indexed[i][1] = i;
        }
        Arrays.sort(indexed, (a, b) -> b[0] - a[0]);
        String[] result = new String[n];
        for (int rank = 0; rank < n; rank++) {
            int idx = indexed[rank][1];
            if (rank == 0)
                result[idx] = "Gold Medal";
            else if (rank == 1)
                result[idx] = "Silver Medal";
            else if (rank == 2)
                result[idx] = "Bronze Medal";
            else
                result[idx] = String.valueOf(rank + 1);
        }
        return result;
    }
}
      

var findRelativeRanks = function(score) {
    const indexed = score.map((sc, idx) => [sc, idx]);
    indexed.sort((a, b) => b[0] - a[0]);
    const result = Array(score.length);
    for (let rank = 0; rank < indexed.length; rank++) {
        const idx = indexed[rank][1];
        if (rank === 0)
            result[idx] = "Gold Medal";
        else if (rank === 1)
            result[idx] = "Silver Medal";
        else if (rank === 2)
            result[idx] = "Bronze Medal";
        else
            result[idx] = String(rank + 1);
    }
    return result;
};
      

Problem Description

You are given an array score of size n, where each element represents the score of an athlete in a competition. Your task is to assign a relative rank to each athlete based on their 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".
• For all other athletes, assign their rank number as a string (e.g., "4", "5", ...), based on their position in the sorted order (1-based).

The result should be an array of strings result where result[i] corresponds to the rank of the athlete at score[i] in the original array. Each athlete should have exactly one rank, and no two athletes can share the same rank.

Thought Process

To solve this problem, we need to determine the relative standing of each athlete based on their score. A brute-force approach might involve repeatedly finding the maximum score and assigning ranks one by one, but this would be inefficient, especially for large arrays.

Instead, we realize that sorting the scores in descending order gives us the ranking order directly. By keeping track of the original indices, we can assign the correct rank to each athlete in the original order. This approach is much more efficient than checking each score individually for its rank.

The key insight is to pair each score with its index, sort these pairs by score, and then assign the appropriate rank string based on each athlete's position in the sorted list.

Solution Approach

Let's break down the steps to solve the problem:

1. Pair Scores with Indices:
   • Create a list of pairs, where each pair contains the score and its original index.
2. Sort the Pairs:
   • Sort the list of pairs in descending order by score. This way, the first item has the highest score, the second item the second highest, and so on.
3. Assign Ranks:
   • Iterate through the sorted list. For the first three athletes, assign "Gold Medal", "Silver Medal", and "Bronze Medal" respectively.
   • For the rest, assign their (1-based) rank as a string, such as "4", "5", etc.
4. Build the Result Array:
   • Since we tracked the original indices, we can place the correct rank string at the appropriate position in the result array.

We use a list or array for the result so that we can efficiently update each athlete's rank by their original index. Sorting is used because it gives us the ranking in O(n log n) time, which is efficient for this problem.

Example Walkthrough

Let's consider the input score = [5, 4, 3, 2, 1].

1. Pair with Indices:
   [(5,0), (4,1), (3,2), (2,3), (1,4)]
2. Sort Descending:
   [(5,0), (4,1), (3,2), (2,3), (1,4)] (already sorted)
3. Assign Ranks:
   • Index 0 (score 5): "Gold Medal"
   • Index 1 (score 4): "Silver Medal"
   • Index 2 (score 3): "Bronze Medal"
   • Index 3 (score 2): "4"
   • Index 4 (score 1): "5"
4. Result:
   ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Notice how each athlete's rank is placed at their original index, preserving the input order.

Time and Space Complexity

Brute-force Approach:

• For each athlete, loop through all scores to count how many are greater (O(n^2)).
• This is slow and not practical for large inputs.

• Pairing scores with indices: O(n)
• Sorting: O(n log n)
• Assigning ranks: O(n)
• Total Time Complexity: O(n log n)
• Space Complexity: O(n) (for pairs and result array)

The optimized approach is efficient and suitable for large input sizes.

Summary

To assign relative ranks to athletes based on their scores, we pair each score with its index, sort these pairs in descending order, and then assign rank strings based on their sorted positions. This method is efficient, easy to implement, and leverages sorting to avoid unnecessary repeated comparisons. The solution is both elegant and practical, making use of data structures and sorting to achieve the desired result efficiently.