Relative Ranks – Leetcode #506

Problem Statement

This problem is from Leetcode – Relative Ranks. The problem statement in short is given below:

Given an array of unique athlete scores, assign ranks where the top three receive "Gold Medal", "Silver Medal", "Bronze Medal", and others receive their numeric rank. Return ranks in original order.

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:

PERFORMANCE ANALYSIS

RUNTIME	14 ms | Beats 16.38 %
MEMORY	45.63 MB | Beats 79.73 %
TIME COMPLEXITY	O (N)