Relative Ranks
Easy · Heap & Counting · Array · Sorting · Heap (Priority Queue)
Problem
You are given an array score of n distinct scores, one per athlete; a higher score is a better result. The athlete with the highest score places 1st, the next highest 2nd, and so on.
Build an array answer where answer[i] describes the placement of athlete i:
- 1st place is "Gold Medal", 2nd place is "Silver Medal", 3rd place is "Bronze Medal".
- Any place p >= 4 is written as the number itself, as a string (for example "4").
Return answer, in the same order as score.
Examples
Input: score = [40,95,70,10] Output: ["Bronze Medal","Gold Medal","Silver Medal","4"]
Sorted from highest the scores are 95, 70, 40, 10, so athlete 3 (score 10) places 4th.
Input: score = [7] Output: ["Gold Medal"]
The only athlete wins.
Input: score = [10,3,8,9,4] Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
From highest: 10, 9, 8, 4, 3. The scores 4 and 3 place 4th and 5th.
Constraints
- n == len(score)
- 1 <= n <= 10^4
- 0 <= score[i] <= 10^6
- All scores are distinct
Approaches
- Max-heap, pop the best one at a time — time O(n log n), space O(n)
Follow-up
If the scores could tie, equal scores would share a place and the next place would skip past them: the place becomes one more than the number of strictly higher scores. If scores are small integers (say at most 10^6), a counting array indexed by score gives the order in O(n + max score) without a comparison sort.
Related problems
Start free on Cariara · Coding problems · System design studio
