506. Relative Ranks
Problem Description
You are given a list of scores for athletes in a competition. Each score in the score
array is unique, and represents the score of an athlete, where score[i]
is the score for the i
th athlete. The goal is to rank the athletes based on their scores in descending order ā the highest score gets the first rank, the second-highest gets the second rank, and so forth.
For the top three ranks, specific strings are used instead of numbers:
- The
1st
place is given the rank "Gold Medal". - The
2nd
place is given the rank "Silver Medal". - The
3rd
place is given the rank "Bronze Medal".
For all other positions starting from the 4th
to the n
th place, the rank is the numeric place of the athlete in the sorted list. The task is to return an array where each element represents the rank of the corresponding athlete in the original input array.
Intuition
The problem can be simplified to sorting the athletes based on their scores and then assigning ranks according to their sorted positions. Since we are interested in the order of scores and need to remember the original indices, we can sort the indexes of the athletes based on the scores they map to. We perform the sort in descending order to ensure that the athlete with the highest score gets the first index.
Once we have the indices sorted by the athletes' scores, we can map these to their respective ranks. For the first three athletes (indices 0
, 1
, and 2
) after sorting, we assign the special ranks ("Gold Medal", "Silver Medal", "Bronze Medal"). For all other athletes, we convert their index position (plus one, since we rank starting from 1
not 0
) to a string to represent their numeric rank. The reason we add 1
is that ranks are typically 1-indexed, not 0-indexed. Finally, we place these rank strings in a new array ans
with the same size as the input array, ensuring that each athlete's rank is placed in their original index in the input array.
Learn more about Sorting and Heap (Priority Queue) patterns.
Solution Approach
The provided Python code implements a solution that carefully maps the athletes' scores to their respective ranks. Here's how the code works in detail, breaking it down into key steps:
- First, we calculate the length of the input
score
array, which represents the number of athletes. This is stored in the variablen
. - We then create a list called
idx
, which is a list of indices from0
ton-1
. These indexes correspond to the positions of athletes in thescore
array. - The
idx
list is sorted using a customkey
function which sorts the indexes based on the scores at those indexes in descending order. The lambda functionlambda x: -score[x]
returns the negative score value for each index, thus ensuring a descending sort. - A
top3
list is defined with the strings "Gold Medal", "Silver Medal", and "Bronze Medal" which are the ranks for the top three athletes. - We create an array
ans
initialized withNone
values, with the same length as the number of athletes. This will be used to store the final rankings. - A loop runs from
0
ton
to assign ranks to all athletes. The current index in the sortedidx
list determines the athlete's placement in the sorted order. - Inside the loop:
- If the index is less than
3
(meaning the athlete is in the top three), we use thetop3
list to assign "Gold Medal", "Silver Medal", or "Bronze Medal" accordingly. - For all other indices (4th place and beyond), we convert the index to a string, while also adding
1
to it to account for the fact that rankings start from1
instead of0
. This string is the athlete's rank.
- If the index is less than
- We assign these ranks to the corresponding positions in the
ans
array based on the sorted indices. This ensures each athlete's rank is placed at the same index as they originally appeared in thescore
array. - Finally, the
ans
array, now filled with the rankings, is returned.
This approach ensures that the athletes are ranked according to their scores, with the original array structure preserved, and special rankings are given to the top three athletes.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Letās walk through a small example to illustrate the solution approach described in the content above. Suppose we have the following list of scores for a competition:
scores = [50, 30, 80, 70, 10]
We want to determine the ranks of these athletes, with the top three receiving "Gold Medal", "Silver Medal", and "Bronze Medal", respectively.
The detailed steps would be:
-
Calculate the length of the scores array,
n = 5
. -
Create a list of indices
idx = [0, 1, 2, 3, 4]
. -
Sort the
idx
list by the athletes' scores in descending order:You will end up with indices sorted as
[2, 3, 0, 1, 4]
because when mapping these indices back to thescores
, you get[80, 70, 50, 30, 10]
which is in descending order. -
Define a list
top3 = ["Gold Medal", "Silver Medal", "Bronze Medal"]
. -
Initialize an array
ans = [None, None, None, None, None]
to store the rankings. -
Loop through indices in idx and assign ranks as follows:
- At idx[0] (which is 2), the score is 80. Since it is the highest, assign "Gold Medal" to
ans[2]
. - At idx[1] (which is 3), the score is 70. Assign "Silver Medal" to
ans[3]
. - At idx[2] (which is 0), the score is 50. Assign "Bronze Medal" to
ans[0]
. - At idx[3] (which is 1), the score is 30. This is the 4th highest score, so assign the string '4' to
ans[1]
. - At idx[4] (which is 4), the score is 10. This is the 5th highest score, so assign the string '5' to
ans[4]
.
The iteration assigns ranks based on the sorted indices and maps them back to the original
ans
array at their respective positions. - At idx[0] (which is 2), the score is 80. Since it is the highest, assign "Gold Medal" to
-
Final
ans
array after the loop will be:
ans = ["Bronze Medal", "4", "Gold Medal", "Silver Medal", "5"]
As shown in the ans
array, we have assigned the correct rank to each athlete based on their original position in the scores
array. Athlete with score 80 (3rd in the original array) gets "Gold Medal", athlete with score 70 (4th in the original array) gets "Silver Medal", and so on.
The final output correctly represents the ranks of the athletes corresponding to their scores in descending order, fulfilling the problem description.
Solution Implementation
1class Solution:
2 def find_relative_ranks(self, scores: List[int]) -> List[str]:
3 # Find the number of scores
4 num_scores = len(scores)
5
6 # Create a list of indices from the scores list
7 indices = list(range(num_scores))
8
9 # Sort indices based on the scores in descending order
10 indices.sort(key=lambda x: -scores[x])
11
12 # Define strings for the top three positions
13 top_three_medals = ['Gold Medal', 'Silver Medal', 'Bronze Medal']
14
15 # Initialize the answer list with placeholders
16 answer = [None] * num_scores
17
18 # Fill the answer list with the appropriate rank strings
19 for rank, index in enumerate(indices):
20 # If the rank is less than 3, assign a medal string
21 if rank < 3:
22 answer[index] = top_three_medals[rank]
23 else:
24 # Otherwise, assign the numeric rank as a string
25 answer[index] = str(rank + 1)
26
27 # Return the completed answer list with ranks
28 return answer
29
1class Solution {
2
3 // Method to find the relative ranks for athletes based on their scores.
4 public String[] findRelativeRanks(int[] scores) {
5 // Get the number of athletes based on the length of scores array.
6 int numAthletes = scores.length;
7
8 // Create a wrapper array to hold the indices of the scores.
9 Integer[] indices = new Integer[numAthletes];
10
11 // Initialize the indices array with values from 0 to numAthletes-1.
12 for (int i = 0; i < numAthletes; ++i) {
13 indices[i] = i;
14 }
15
16 // Sort the indices array based on the scores in descending order.
17 // The comparison function uses the scores at the indices to sort the indices.
18 Arrays.sort(indices, (a, b) -> Integer.compare(scores[b], scores[a]));
19
20 // Create an array to hold the answers (relative ranks as strings).
21 String[] ranks = new String[numAthletes];
22
23 // Create an array to hold the medals for the top 3 athletes.
24 String[] medals = new String[] {"Gold Medal", "Silver Medal", "Bronze Medal"};
25
26 // Assign the appropriate rank to each athlete in the ranks array.
27 for (int i = 0; i < numAthletes; ++i) {
28 // If the rank is within the top 3, assign the corresponding medal.
29 if (i < 3) {
30 ranks[indices[i]] = medals[i];
31 } else {
32 // Otherwise, assign the rank number as a string (1-indexed).
33 ranks[indices[i]] = String.valueOf(i + 1);
34 }
35 }
36
37 // Return the array of ranks.
38 return ranks;
39 }
40}
41
1#include <vector>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 // This method finds and returns the relative ranks of athletes based on their scores.
10 vector<string> findRelativeRanks(vector<int>& scores) {
11 int numOfScores = scores.size();
12
13 // Use a vector of pairs to keep track of the scores and their original indices.
14 vector<pair<int, int>> indexedScores;
15 for (int i = 0; i < numOfScores; ++i) {
16 indexedScores.push_back(make_pair(scores[i], i));
17 }
18
19 // Sort the indexed scores in descending order using a custom comparator lambda function.
20 sort(indexedScores.begin(), indexedScores.end(),
21 [](const pair<int, int>& a, const pair<int, int>& b) { return a.first > b.first; });
22
23 // Initialize the answer vector with the same size as the number of scores.
24 vector<string> ranks(numOfScores);
25
26 // Define medals for the top 3 scores.
27 vector<string> medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
28
29 // Assign ranks to the athletes based on sorted order.
30 for (int i = 0; i < numOfScores; ++i) {
31 if (i < 3) {
32 // Assign medals to the top 3 scores.
33 ranks[indexedScores[i].second] = medals[i];
34 } else {
35 // For others, assign the rank as a string (1-indexed).
36 ranks[indexedScores[i].second] = to_string(i + 1);
37 }
38 }
39
40 return ranks;
41 }
42};
43
1// Import the necessary functionalities from corresponding modules
2import { sort } from 'algorithm';
3import { vector, pair, make_pair } from 'vector';
4import { string } from 'string';
5
6// Define a function to find and return the relative ranks of athletes based on their scores.
7function findRelativeRanks(scores: number[]): string[] {
8 const numOfScores: number = scores.length;
9
10 // Create an array to keep track of the scores along with their original indices.
11 const indexedScores: Array<pair<number, number>> = [];
12 for (let i = 0; i < numOfScores; ++i) {
13 indexedScores.push(make_pair(scores[i], i));
14 }
15
16 // Use a custom comparator function for sorting the indexed scores in descending order.
17 indexedScores.sort((a: pair<number, number>, b: pair<number, number>): number => b.first - a.first);
18
19 // Prepare an array to hold the rank strings, initially empty.
20 const ranks: string[] = new Array<string>(numOfScores);
21
22 // Define medal strings for the top 3 ranks.
23 const medals: string[] = ["Gold Medal", "Silver Medal", "Bronze Medal"];
24
25 // Loop through the sorted scores to assign ranks or medals.
26 for (let i = 0; i < numOfScores; ++i) {
27 if (i < 3) {
28 // Assign medals to the top 3 athletes.
29 ranks[indexedScores[i].second] = medals[i];
30 } else {
31 // For the other athletes, assign their rank as a string (1-indexed).
32 ranks[indexedScores[i].second] = (i + 1).toString();
33 }
34 }
35
36 return ranks;
37}
38
39// The TypeScript syntax requires type annotations for parameters and variables.
40// The standard JavaScript Array and sort functions are used in place of std::vector and std::sort.
41// Note: TypeScript does not have an equivalent of std::pair, but you can use tuples or define an interface.
42
43// Note: The above code block is written with the assumption that the TypeScript environment would mimic C++ functionality and modules, which is not the case in a standard TypeScript/JavaScript setup.
44// In a standard TypeScript environment, the `algorithm` or `vector` modules do not exist, and JavaScript's array methods would be used for tasks such as sorting.
45
Time and Space Complexity
The time complexity of the provided findRelativeRanks
function is O(n log n)
where n
is the number of athletes (the length of the input score
list). This is because the function is performing a sort operation on a list of n
indices, which is the most time-consuming part of the algorithm. The sorting function itself has a time complexity of O(n log n)
.
After sorting, the function traverses the sorted indices once, creating a result list of ranks. This traversal is linear with respect to the number of athletes, giving it a time complexity of O(n)
. However, this linear traversal does not dominate the sorting complexity, so the overall time complexity remains O(n log n)
.
The space complexity of the algorithm is O(n)
. We have idx
and ans
lists, each of size n
. The top3
list is of constant size and does not scale with n
, so it does not affect the asymptotic space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!