You are given an integer array score of size n, where score[i] is the score of the ith athlete in a competition. All the scores are guaranteed to be unique.
The athletes are placed based on their scores, where the 1st place athlete has the highest score, the 2nd place athlete has the 2nd highest score, and so on. The placement of each athlete determines their rank:
1st place athlete's rank is "Gold Medal".2nd place athlete's rank is "Silver Medal".3rd place athlete's rank is "Bronze Medal".4th place to the nth place athlete, their rank is their placement number (i.e., the xth place athlete's rank is "x").Return an array answer of size n where answer[i] is the rank of the ith athlete.
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.length1 <= n <= 1040 <= score[i] <= 106score are unique.Problem Overview: You are given an array of scores where each element represents an athlete’s score. The highest score gets "Gold Medal", the second highest gets "Silver Medal", the third gets "Bronze Medal", and the rest receive their numeric rank based on score order. The result must be returned in the same order as the original array.
Approach 1: Sorting with Index Mapping (O(n log n) time, O(n) space)
This approach sorts athletes by score while preserving their original positions. Create a list of pairs (score, index), then sort it in descending order using a standard sorting algorithm. After sorting, iterate through the list and assign ranks based on the sorted position: the first three positions map to medal strings and the rest get their rank number as a string. Use the stored indices to place the rank back into the correct position in the result array. The main cost comes from sorting, which takes O(n log n) time, while the additional array for storing pairs results in O(n) extra space.
Approach 2: HashMap to Determine Ranks (O(n log n) time, O(n) space)
This method separates ranking from result construction using a hash map. First, create a copy of the score array and sort it in descending order. Next, iterate through the sorted array and store each score’s rank in a HashMap where the key is the score and the value is its rank position. Once the ranking map is built, iterate through the original score array and look up each score’s rank in constant time. Convert the first three ranks to medal labels and keep numeric ranks for the rest. Hash lookups run in O(1) average time, so the overall complexity is dominated by sorting at O(n log n) with O(n) additional memory for the map. This approach highlights the use of arrays and hash-based lookups to simplify rank retrieval.
Both approaches rely on ordering scores globally. A heap (priority queue) could also track the highest scores incrementally, but sorting is simpler and usually faster in practice for this problem size.
Recommended for interviews: Sorting with index mapping is the expected solution. It clearly demonstrates how to maintain original positions while ranking sorted data. Interviewers typically accept the HashMap variant as well, but the index mapping approach is more direct and avoids an additional lookup structure. Showing the sorting strategy first demonstrates solid understanding of ranking problems and array manipulation.
The idea is to sort the scores but preserve their original indices by pairing each score with its index. Once sorted, we can easily determine their ranks by iterating over the sorted list. We then assign the corresponding rank values based on their positions (i.e., 'Gold Medal' for the first position, etc.). This approach utilizes additional space to maintain the original indices while sorting the scores.
The solution involves creating a pair structure (ScoreIndex) to hold both the score and its original index. We make use of qsort to sort the array in descending order based on scores. After sorting, the rank is assigned according to the sorted position, converting the top three into medal strings and others into strings of their positions. Finally, the ranks are filled into the result array based on original indices.
Time Complexity: O(n log n), where n is the number of scores, for the sorting operation.
Space Complexity: O(n) for storing the pair struct array and the result array.
In this approach, we employ a hash map (or dictionary) to map each score to its ranking position in a sorted list. The scores are first sorted to determine order-based ranks. We then iterate through original scores, using the map to quickly assign the appropriate ranking (medal or numeric) to each score.
This C solution sorts a copy of the original list and uses the sorted positions to determine ranks. The qsort function provides a sorted view, and scores are ranked by finding their positions in this sorted list. Medals are assigned for the top three ranks using conditional checks.
Time Complexity: O(n log n) from sorting.
Space Complexity: O(n) due to storage of the sorted copy.
We use an array idx to store the indices from 0 to n-1, then sort idx based on the values in score in descending order.
Next, we define an array top3 = [Gold Medal, Silver Medal, Bronze Medal]. We traverse idx, and for each index j, if j is less than 3, then ans[j] is top3[j]; otherwise, it is j+1.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array score.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting with Index Mapping | Time Complexity: O(n log n), where n is the number of scores, for the sorting operation. |
| HashMap to Determine Ranks | Time Complexity: O(n log n) from sorting. |
| Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting with Index Mapping | O(n log n) | O(n) | General solution when you need to rank values but keep original indices |
| HashMap to Determine Ranks | O(n log n) | O(n) | Useful when separating rank computation from final result lookup |
Relative Ranks | 3 Approaches | Leetcode 506 | codestorywithMIK • codestorywithMIK • 5,609 views views
Watch 9 more video solutions →Practice Relative Ranks with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor