Rank Scores - Leetcode Solution

Problem Statement: Given a list of scores, return the relative ranks of each score. The relative rank of a score is defined as its position in the sorted list, where 1 represents the highest rank. If two scores have the same relative rank, they should have the same rank.

Example: Input: [10,3,8,9,4] Output: ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

Solution Approach: We can solve this problem using a hashmap to store the original index of each score. We can then sort the scores in decreasing order and assign ranks based on the sorted order.

Algorithm:

1. Create a hashmap to store the original index of each score.
2. Sort the scores in decreasing order.
3. Assign ranks based on the sorted order.
4. For scores with the same rank, assign the same rank.
5. Transform ranks into medal names.
6. Return the result.

Pseudo Code: def findRelativeRanks(self, nums: List[int]) -> List[str]: # create a hashmap to store the original index of each score index_map = {} for i in range(len(nums)): index_map[nums[i]] = i

# sort scores in decreasing order
sorted_scores = sorted(nums, reverse=True)

# assign ranks based on the sorted order
ranks = {}
for i in range(len(sorted_scores)):
    if i == 0:
        ranks[sorted_scores[i]] = "Gold Medal"
    elif i == 1:
        ranks[sorted_scores[i]] = "Silver Medal"
    elif i == 2:
        ranks[sorted_scores[i]] = "Bronze Medal"
    else:
        ranks[sorted_scores[i]] = str(i + 1)

# assign the same rank for scores with the same value
result = [0] * len(nums)
for i in range(len(sorted_scores)):
    result[index_map[sorted_scores[i]]] = ranks[sorted_scores[i]]

return result

Time Complexity: The time complexity of this algorithm is O(n log n), as we are sorting the scores.

Space Complexity: The space complexity of this algorithm is O(n), as we are creating a hashmap to store the original index of each score.

1