Relative Ranks – Leetcode #506

Problem Statement

This problem is from Leetcode – Relative Ranks. 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., 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.

Solution

To solve the problem of ranking athletes based on their unique scores, we can follow these steps:

1. First, we need to sort the athletes based on their scores in descending order to determine their placements.
2. Push the scores and their corresponding indices into a HashMap.
3. Map Ranks Back to Original Indices, we need to return the ranks in the order corresponding to the original indices of the athletes.
4. We will assign “Gold Medal” to the athlete with the highest score, “Silver Medal” to the second highest, “Bronze Medal” to the third highest, and for all other athletes, we will assign ranks based on their placements.

See the code sample below:

public String[] findRelativeRanks(int[] score) {

		String[] placements = new String[score.length];
		
		// convert to Integer array
		Integer[] sortedScore = new Integer[score.length];
		Arrays.setAll(sortedScore, i -> score[i]);
		
		// sort in descending order
		Arrays.sort(sortedScore, Collections.reverseOrder());
		
		// push the scores and the corresponding indices into a HashMap
		Map<Integer, Integer> scoreMap = new HashMap<Integer, Integer>();
		for(int i=0; i<score.length; i++) {

			scoreMap.put(sortedScore[i], i);
		}

		int index = 0;
		
		// now assign the placements
		for(int i = 0; i < score.length; i++) {

			index = scoreMap.get(score[i]);

			if(index == 0) {

				placements[i] = "Gold Medal";
			}
			else if(index == 1) {

				placements[i] = "Silver Medal";
			}
			else if(index == 2) {

				placements[i] = "Bronze Medal";
			}
			else {

				placements[i] = "" + (index+1) + "";

			}
		}

		return placements;

	}

You can checkout the code from Github here: Relative Ranks – First Approach. See the performance of this approach below: