Leetcode 506. Relative Ranks

Problem Explanation

The problem requires us to find the relative ranks of athletes based on their scores. The top three athletes will receive medals: "Gold Medal", "Silver Medal", "Bronze Medal". For the rest of the athletes, we just need to output their ranks as strings.

For instance, if we have five athletes with scores [5,4,3,2,1], the ranks will be ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"].

The problem also provides that N, the number of athletes is a positive integer and does not exceed 10,000. All scores of athletes are unique.

To solve this problem, we use the sorting algorithm. The idea is to make pairs of scores and indices and sort this list in descending order of scores. After that, we simply assign the medals and ranks according to the sorted order.

Solution Walkthrough

For the example [5,4,3,2,1], the initial index-score pairs look like:

[(5,1), (4,2), (3,3), (2,4), (1,5)]

The Sorted index-score pairs would be:

[(1, 'Gold Medal'), (2, 'Silver Medal'), (3, 'Bronze Medal'), (4, '4'), (5, '5')]

So, we simply return the second element from each tuple of the pairs list as our final ranks list.

Python Solution

1
2python
3class Solution:
4  def findRelativeRanks(self, nums):
5    sorted_nums = sorted([(score, i) for i, score in enumerate(nums)], reverse=True)
6    for i, (score, index) in enumerate(sorted_nums):
7      if i == 0:
8        nums[index] = "Gold Medal"
9      elif i == 1:
10        nums[index] = "Silver Medal"
11      elif i == 2:
12        nums[index] = "Bronze Medal"
13      else:
14        nums[index] = str(i + 1)
15    return nums

Java Solution

1
2java
3class Solution {
4    public String[] findRelativeRanks(int[] nums) {
5        int[][] pair = new int[nums.length][2];
6        for (int i = 0; i < nums.length; i++) {
7            pair[i][0] = nums[i];
8            pair[i][1] = i;
9        }
10
11        Arrays.sort(pair, (a, b) -> (b[0] - a[0]));
12
13        String[] result = new String[nums.length];
14        for (int i = 0; i < nums.length; i++) {
15            if (i == 0)
16                result[pair[i][1]] = "Gold Medal";
17            else if (i == 1)
18                result[pair[i][1]] = "Silver Medal";
19            else if (i == 2)
20                result[pair[i][1]] = "Bronze Medal";
21            else
22                result[pair[i][1]] = String.valueOf(i + 1);
23        }
24
25        return result;
26    }
27}

JavaScript solution

1
2js
3var findRelativeRanks = function(nums) {
4    let sorted = Array.from(nums).sort((a, b) => b - a);
5    return nums.map((n) => {
6        if (n === sorted[0]) return 'Gold Medal';
7        if (n === sorted[1]) return 'Silver Medal';
8        if (n === sorted[2]) return 'Bronze Medal';
9        return String(sorted.indexOf(n) + 1);
10    });
11};

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<string> findRelativeRanks(vector<int>& nums) {
6        // make the pair of score and their indices
7        int n = nums.size();
8        vector<pair<int,int>> vec(n);
9        for(int i = 0; i < n; i++) vec[i] = make_pair(nums[i],i);
10        sort(rbegin(vec),rend(vec));
11        
12        vector<string> result(n);
13        for(int i = 0; i < n; i++) {
14            if (i == 0) result[vec[i].second] = "Gold Medal";
15            else if(i == 1) result[vec[i].second] = "Silver Medal";
16            else if(i == 2) result[vec[i].second] = "Bronze Medal";
17            else result[vec[i].second] = to_string(i+1);
18        }
19        return result;
20    }
21};

C# Solution

1
2csharp
3public class Solution {
4    public string[] FindRelativeRanks(int[] nums) {
5        int l = nums.Length;
6        int[] index = new int[l];
7        string[] result = new string[l];
8
9        for(int i=0; i < l; i++) {
10            index[i] = i;
11        }
12
13        Array.Sort(index, (a,b)=>(nums[b].CompareTo(nums[a])));
14        
15        for(int i=0;i<l;i++){
16            if(i==0) result[index[i]] = "Gold Medal";
17            else if(i==1) result[index[i]] = "Silver Medal";
18            else if(i==2) result[index[i]] = "Bronze Medal";
19            else result[index[i]] = String.valueOf(i + 1);
20        }
21
22        return result;
23    }
24}

In the solutions presented above, the athletes' scores are mapped to their respective indices. Then, for each score in the sorted scores array, we assign the awards for the top three ranks and assign rank numbers for the other athletes.# Ruby Solution

1
2ruby
3def find_relative_ranks(nums)
4  sorted = nums.sort.reverse
5  nums.map! do |num|
6    rank = sorted.index(num) + 1
7    if rank == 1
8      'Gold Medal'
9    elsif rank == 2
10      'Silver Medal'
11    elsif rank == 3
12      'Bronze Medal'
13    else
14      rank.to_s
15    end
16  end
17end

In this Ruby solution, the find_relative_ranks function accepts a list of athletes' scores. First, the scores are sorted in descending order. Then, for each score in the original list, we find its index in the sorted list (which represents the rank), and convert the top 3 ranks into their respective medal names, while the rest of the ranks are converted into strings.

The nums.map! is used to transform in-place every element in the original list with their respective rank names.

Swift Solution

1
2swift
3class Solution {
4    func findRelativeRanks(_ score: [Int]) -> [String] {
5        var sorted = score
6        sorted.sort(by: >)
7        
8        var rankDict = [Int: String]()
9        for (index, value) in sorted.enumerated() {
10            switch index {
11            case 0:
12                rankDict[value] = "Gold Medal"
13            case 1:
14                rankDict[value] = "Silver Medal"
15            case 2:
16                rankDict[value] = "Bronze Medal"
17            default:
18                rankDict[value] = String(index + 1)
19            }
20        }
21        
22        return score.map { rankDict[$0]! }
23    }
24}

In this Swift solution, findRelativeRanks function also accepts an array of scores. The scores are sorted in descending order. Then, we loop through each element in the array, enumerate the index (zero indexed) and value, and check its rank. If it's in the top 3, we add it as a key-value pair in our dictionary as the score and its respective medal name, otherwise it's stored as its numeric rank. Then we return a new array by using map to get the ranks from the dictionary by the original score array.

These are straightforward ways of solving the problem using different programming languages. As evident, the choice of language can influence the syntax, but the core logic remains the same: map each score to its corresponding rank, and then converting them into their respective medal names for the top 3.


Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ