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.