506 Relative Ranks

1. Description

You are given an integer array score of size n, where score[i] is the score of the ith athelete in a competition. All the scores are guaranteed to be unique.

 

The atheltes are placed based on their scores, where the 1st place athlete has the highest score, the 2nd place athelete has the 2nd highest score, and so on.

• 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., 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.

 

constraints :

• n == score.length
• 1 <= n <= \(10^{4}\)
• 0 <= score[i] <= \(10^{6}\)
• All the values in score are unique.

2. Algorithms

A 'Priority Queue' is a special type of queue in which each element is associated with a priority value. Generally, the value of the element itself is considered for assigning the priority. So, the element with the highest value is considered the highest priority element.

 

So we will apply max heap to make priority queue.

 

To store the rank of the ith athelete preventing original index of input list score, we need to store original index first. We will use dictionary data structure that its key will store original value preventing original index and its value will store the rank of the ith athlete.

 

After store elements of score as a ket of dictionary.

 

1. Start
2. Declare variable n initialized with length of score.
3. Declare variable dict_ initialized with empty dictionary.
4. Repeat steps through values of score.
   1. Store value as key of dict_ and initialize value to 0.
5. Heapify the input list score.
6. Repeat the steps until n == 0.
   1. Pop the element from the heap, score.
   2. If n is bigger than 3, store current index as a value of poped element from heap.
   3. If n is 3, store "Bronze Medal" as a value of poped element from heap.
   4. If n is 2, store "Silver Medal" as a value of poped element from heap.
   5. If n is 1, store "Gold Medal" as a value of poped element from heap.
   6. Increment n by -1.
7. Return values of dict_
8. End

3. Codes

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        n = len(score) 
        dict_ = {} 
        for sc in score : 
            dict_[sc] = 0
            
        heapify(score)
        while n > 0 : 
            sc = heappop(score) 
            if n > 3 : 
                dict_[sc] = str(n) 
            elif n == 3 : 
                dict_[sc] = "Bronze Medal"
            elif n == 2 : 
                dict_[sc] = "Silver Medal"
            else : 
                dict_[sc] = "Gold Medal"
                
            n -= 1
            
        return dict_.values()

 

4. Conclusion