Solution For Rank Scores

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.

Step by Step Implementation For Rank Scores

import java.util.*; 

class Solution 
{ 
    public static void main(String[] args) 
    { 
        int[] arr = {37, 12, 28, 9, 100, 56, 80, 5, 12, 24}; 
        System.out.println("Ranking of Scores:"); 
        printRank(arr); 
    } 
    public static void printRank(int[] arr) 
    { 
        Map map = new HashMap<>(); 
        List list = new ArrayList<>(); 
        for (int i : arr) 
        { 
            list.add(i); 
        } 
        Collections.sort(list, Collections.reverseOrder()); 
        int rank = 1; 
        for (int i : list) 
        { 
            map.put(i, rank); 
            rank++; 
        } 
        for (int i : arr) 
        { 
            System.out.println(map.get(i)); 
        } 
    } 
}

def rankScores(self, scores):

# create a list to store the results

results = []

# get the unique scores

unique_scores = set(scores)

# sort the unique scores in descending order

sorted_scores = sorted(unique_scores, reverse=True)

# for each score in the sorted list

for score in sorted_scores:

# find the number of people with that score

num_people = scores.count(score)

# add the score and the number of people to the results list

results.append([score, num_people])

# return the results list

return results

var rankScores = function(scores, alice) {
    // create a map of score => rank
    let map = {};
    let rank = 1;
    for (let i = 0; i < scores.length; i++) {
        if (!map[scores[i]]) {
            map[scores[i]] = rank;
            rank++;
        }
    }
    
    // map each of Alice's scores to their rank
    let aliceRanks = [];
    for (let i = 0; i < alice.length; i++) {
        let score = alice[i];
        if (map[score]) {
            aliceRanks.push(map[score]);
        } else {
            // find the next highest score
            let nextHighest = Infinity;
            for (let key in map) {
                if (key > score && key < nextHighest) {
                    nextHighest = key;
                }
            }
            
            // if there is no next highest score, Alice is last
            if (nextHighest === Infinity) {
                aliceRanks.push(rank);
            } else {
                // Alice's rank is between the current highest and next highest
                aliceRanks.push(map[nextHighest] + 1);
            }
        }
    }
    
    return aliceRanks;
};

vector Solution::solve(vector &A) {
    // Do not write main() function.
    // Do not read input, instead use the arguments to the function.
    // Do not print the output, instead return values as specified
    // Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
    
    sort(A.begin(), A.end());
    
    int n = A.size();
    
    int curr_rank = 1;
    
    for (int i = 0; i < n; i++) {
        if (i > 0 && A[i] == A[i-1]) {
            continue;
        }
        A[i] = curr_rank;
        curr_rank++;
    }
    
    return A;
}

using System; 
using System.Collections.Generic; 
using System.Linq; 

public class Test 
{ 
    public static void Main() 
    { 
        int[] scores = {100, 90, 90, 80, 75, 60}; 
        string[] alphabets = {"a", "b", "c", "d", "e", "f"}; 
        List> list = new List>(); 
        for(int i = 0; i < scores.Length; i++) 
        { 
            list.Add(new KeyValuePair(scores[i], alphabets[i])); 
        } 

        // Sort the list by key in descending order 
        list.Sort((pair1, pair2) => pair2.Key.CompareTo(pair1.Key)); 

        // Take the list of key value pairs and convert it to a dictionary 
        Dictionary dict = list.ToDictionary(pair => pair.Key, pair => pair.Value); 

        // Iterate through the dictionary and print the values 
        foreach(KeyValuePair kvp in dict) 
        { 
            Console.WriteLine(kvp.Value); 
        } 
    } 
}