Relative Ranks

Difficulty: Easy | Acceptance: 74.60% | Paid: No Topics: Array, Sorting, Heap (Priority Queue)

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:

The 1st place athlete’s rank is “Gold Medal”. The 2nd place athlete’s rank is “Silver Medal”. The 3rd place athlete’s rank is “Bronze Medal”. For the 4th place to the nth place athlete, their rank is their placement number (i.e., 4th place athlete’s rank is “4”).

Return an array answer of size n such that answer[i] is the rank of the ith athlete.

• Examples
• Constraints
• Sorting with Index Tracking
• Max Heap Approach
• Copy and Sort with Map

Examples

Example 1:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The first athlete has the highest score (5) and gets "Gold Medal". The second athlete has the second highest score (4) and gets "Silver Medal". The third athlete has the third highest score (3) and gets "Bronze Medal". The fourth athlete has the fourth highest score (2) and gets "4". The fifth athlete has the fifth highest score (1) and gets "5".

Example 2:

Input: score = [10,3,8,9,4]
Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
Explanation: The first athlete has the highest score (10) and gets "Gold Medal". The second athlete has the second highest score (9) and gets "Silver Medal". The third athlete has the third highest score (8) and gets "Bronze Medal". The fourth athlete has the fourth highest score (4) and gets "4". The fifth athlete has the fifth highest score (3) and gets "5".

Constraints

- n == score.length
- 1 <= n <= 10^4
- 0 <= score[i] <= 10^6
- All the values in score are unique.

Sorting with Index Tracking

Intuition Create pairs of (score, original index), sort by score in descending order, then assign ranks based on sorted position.

Steps

• Create an array of pairs containing (score, original index)
• Sort the array in descending order by score
• Iterate through sorted array and assign ranks to result at original indices
• Use “Gold Medal”, “Silver Medal”, “Bronze Medal” for first three positions

class Solution:
    def findRelativeRanks(self, score: list[int]) -> list[str]:
        n = len(score)
        indexed_scores = [(score[i], i) for i in range(n)]
        indexed_scores.sort(reverse=True, key=lambda x: x[0])
        
        result = [None] * n
        medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
        
        for rank, (_, original_idx) in enumerate(indexed_scores):
            if rank < 3:
                result[original_idx] = medals[rank]
            else:
                result[original_idx] = str(rank + 1)
        
        return result

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Simple and intuitive approach using sorting

Max Heap Approach

Intuition Use a max heap to extract scores in descending order while tracking original indices for rank assignment.

Steps

• Create a max heap with (score, index) pairs
• Extract elements one by one from heap
• Assign ranks based on extraction order
• Handle special medal names for top 3

import heapq

class Solution:
    def findRelativeRanks(self, score: list[int]) -> list[str]:
        n = len(score)
        max_heap = [(-score[i], i) for i in range(n)]
        heapq.heapify(max_heap)
        
        result = [None] * n
        medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
        
        for rank in range(n):
            _, original_idx = heapq.heappop(max_heap)
            if rank < 3:
                result[original_idx] = medals[rank]
            else:
                result[original_idx] = str(rank + 1)
        
        return result

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Heap operations are O(log n) each, performed n times

Copy and Sort with Map

Intuition Create a sorted copy of scores, then use a hash map to map each score to its rank for O(1) lookup.

Steps

• Create a copy of scores array and sort it in descending order
• Build a hash map from score to rank
• Iterate through original scores and look up ranks from map
• Handle special medal names for top 3

class Solution:
    def findRelativeRanks(self, score: list[int]) -> list[str]:
        sorted_score = sorted(score, reverse=True)
        score_to_rank = {}
        
        for rank, s in enumerate(sorted_score):
            if rank == 0:
                score_to_rank[s] = "Gold Medal"
            elif rank == 1:
                score_to_rank[s] = "Silver Medal"
            elif rank == 2:
                score_to_rank[s] = "Bronze Medal"
            else:
                score_to_rank[s] = str(rank + 1)
        
        return [score_to_rank[s] for s in score]

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Clean approach using hash map for O(1) rank lookup