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.In #506 Relative Ranks, you are given an array representing athletes' scores and must assign ranks based on their performance. The highest score gets "Gold Medal", the second gets "Silver Medal", the third gets "Bronze Medal", and the remaining athletes receive their numeric rank.
A common approach is to sort the scores while keeping track of their original indices. After sorting in descending order, iterate through the sorted list and assign the correct medal or rank string based on the position. Then place the result back into the output array using the stored indices.
Another approach uses a max heap (priority queue) to repeatedly extract the highest score and assign ranks in order. This also ensures the highest-performing athletes are processed first.
The sorting method is usually simpler and widely used in interviews. Its time complexity is dominated by sorting, while additional space is used to store indices and results.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting with index tracking | O(n log n) | O(n) |
| Max Heap (Priority Queue) | O(n log n) | O(n) |
code Explainer
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5struct ScoreIndex {
6 int score
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.
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.
Time Complexity: O(n log n) from sorting.
Space Complexity: O(n) due to storage of the sorted copy.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Relative Ranks is a common easy-level interview problem used to test understanding of sorting, heaps, and array manipulation. It often appears in coding practice platforms and interview preparation lists.
Arrays combined with sorting are typically the best choice for this problem. Alternatively, a max heap (priority queue) can be used to repeatedly extract the highest score and assign ranks in order.
The most common approach is to sort the scores in descending order while keeping track of their original indices. After sorting, assign medals to the top three and numeric ranks to the rest. This method is efficient and easy to implement with O(n log n) time complexity.
Sorting changes the order of elements, but the final ranks must correspond to the athletes' original positions. Storing indices allows you to map the computed rank back to the correct position in the result array.
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.