506. Relative Ranks
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 51.5%
Problem Breakdown
The problem requires assigning ranks to athletes based on their scores in descending order. The highest score gets the “Gold Medal”, the second-highest gets the “Silver Medal”, and the third-highest gets the “Bronze Medal”. All other scores are ranked by their position (e.g., 4th place, 5th place). The input is an array of unique scores, and the output should be an array of corresponding ranks.
Inputs:
- An integer array
scorewhere each element represents a unique score of an athlete.
Outputs:
- A string array
answerwhere each element is the rank of the corresponding athlete in the input array.
Implicit Constraints/Edge Cases:
- The length of the input array can range from 1 to 10,000.
- All scores are unique and non-negative integers up to 1,000,000.
- Edge cases include:
- An empty input array (though the problem guarantees at least one score).
- Scores that are all the same (not applicable due to uniqueness constraint).
Intuition
A brute-force approach would involve sorting the scores and then mapping each original score to its rank. However, this would require additional space for storing sorted scores and could be inefficient in terms of time complexity.
The key insight is to use a max-heap (priority queue) to efficiently get the highest scores one by one without needing to sort the entire array. This allows us to assign ranks directly based on the order of extraction from the heap.
Approach
- Create a Max-Heap: Convert the input scores into a max-heap to easily extract the highest scores.
- Assign Ranks: Use a dictionary to map each score to its rank as we extract it from the heap.
- Construct the Result: Iterate through the original scores and use the dictionary to get the corresponding ranks.
Data Structures:
- A max-heap (priority queue) to efficiently get the highest scores.
- A dictionary to store the mapping of scores to their ranks.
Complexity Analysis
- Time Complexity: (O(n \log n))
- Building a max-heap takes (O(n \log n)).
- Extracting elements from the heap and assigning ranks also takes (O(n \log n)).
- Space Complexity: (O(n))
- Storing the heap and the dictionary both require (O(n)) space.
Solution
import heapq
def findRelativeRanks(score):
# Create a max-heap by negating scores (since Python's heapq is min-heap by default)
max_heap = [-s for s in score]
heapq.heapify(max_heap)
# Dictionary to store the rank of each score
rank_dict = {}
rank_names = ["Gold Medal", "Silver Medal", "Bronze Medal"]
# Assign ranks based on the order of extraction from the heap
while max_heap:
current_score = -heapq.heappop(max_heap)
if len(rank_dict) < 3:
rank_dict[current_score] = rank_names[len(rank_dict)]
else:
rank_dict[current_score] = str(len(rank_dict) + 1)
# Construct the result array based on the original scores
answer = [rank_dict[s] for s in score]
return answer
# Example usage:
print(findRelativeRanks([5,4,3,2,1])) # Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
print(findRelativeRanks([10,3,8,9,4])) # Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
Edge Cases Handled
- Empty Input: The problem guarantees at least one score, so this edge case is not applicable.
- Unique Scores: The uniqueness constraint ensures that no two scores are the same, simplifying rank assignment.