Relative Ranks

LeetCode 506 | Difficulty: Easy

Easy

Problem Description

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

The athletes are placed based on their scores, where the 1^st place athlete has the highest score, the 2^nd place athlete has the 2^nd highest score, and so on. The placement of each athlete determines their rank:

• The 1^st place athlete's rank is "Gold Medal".

• The 2^nd place athlete's rank is "Silver Medal".

• The 3^rd place athlete's rank is "Bronze Medal".

• For the 4^th place to the n^th place athlete, their rank is their placement number (i.e., the x^th place athlete's rank is "x").

Return an array answer of size n where answer[i] is the rank of the i^th athlete.

Example 1:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1^st, 2^nd, 3^rd, 4^th, 5^th].

Example 2:

Input: score = [10,3,8,9,4]
Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
Explanation: The placements are [1^st, 5^th, 3^rd, 2^nd, 4^th].

Constraints:

• n == score.length

• 1 <= n <= 10^4

• 0 <= score[i] <= 10^6

• All the values in score are unique.

Topics: Array, Sorting, Heap (Priority Queue)

---

Approach

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 348 ms)

Metric	Value
Runtime	348 ms
Memory	N/A
Date	2018-04-18

Solution

public class Solution {
    public string[] FindRelativeRanks(int[] nums) {
        	var sortedNums = nums.ToList().ToArray();
	Array.Sort(sortedNums);
	int n = nums.Length;
	string[] medals = new string[] {"Gold Medal", "Silver Medal", "Bronze Medal"};
	Dictionary<int,string> ranks = new Dictionary<int,string>();
	string[] result = new string[n];
	int rank = 4;
	for (int i = n-4; i >= 0; i--)
	{
		ranks.Add(sortedNums[i], $"{rank++}");
	}
	int  j=0;
	for (int i = n-1; i >= n-3 && i>=0; i--)
	{
		ranks.Add(sortedNums[i],medals[j++]);
	}

	for (int i = 0; i < n; i++)
	{
		result[i] = ranks[nums[i]];
	}
	return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.