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.