Relative Ranks

easy array sorting heap

Problem

Given distinct integer scores, return a string array where ans[i] is the rank of athlete i. The top three are "Gold Medal", "Silver Medal", "Bronze Medal"; the rest are their 1-based rank as a string.

Inputscore = [10, 3, 8, 9, 4]

Output["Gold Medal","5","Bronze Medal","Silver Medal","4"]

Sorted descending: 10, 9, 8, 4, 3 → ranks 1..5 written back to original positions.

score (comma-separated, distinct)

def find_relative_ranks(score):
    medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
    order = sorted(range(len(score)), key=lambda i: -score[i])
    ans = [""] * len(score)
    for rank, i in enumerate(order):
        ans[i] = medals[rank] if rank < 3 else str(rank + 1)
    return ans

function findRelativeRanks(score) {
  const medals = ["Gold Medal", "Silver Medal", "Bronze Medal"];
  const order = score.map((s, i) => i).sort((a, b) => score[b] - score[a]);
  const ans = new Array(score.length).fill("");
  order.forEach((i, rank) => {
    ans[i] = rank < 3 ? medals[rank] : String(rank + 1);
  });
  return ans;
}

class Solution {
    public String[] findRelativeRanks(int[] score) {
        String[] medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        Integer[] order = new Integer[score.length];
        for (int i = 0; i < score.length; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> score[b] - score[a]);
        String[] ans = new String[score.length];
        for (int r = 0; r < order.length; r++) {
            ans[order[r]] = r < 3 ? medals[r] : String.valueOf(r + 1);
        }
        return ans;
    }
}

vector<string> findRelativeRanks(vector<int>& score) {
    vector<string> medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
    int n = score.size();
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b){ return score[a] > score[b]; });
    vector<string> ans(n);
    for (int r = 0; r < n; r++) {
        ans[order[r]] = r < 3 ? medals[r] : to_string(r + 1);
    }
    return ans;
}

Explanation

The key idea is to figure out the finishing order of the athletes first, then write each athlete's label back to their original spot. We do this by sorting the indices, not the scores themselves.

We build a list order of the index positions and sort it by score from highest to lowest. After sorting, order[0] is the index of the best athlete, order[1] the second best, and so on.

Now we walk through order by rank. The first three get "Gold Medal", "Silver Medal", and "Bronze Medal"; everyone after that gets their rank as a string, which is rank + 1 (because rank counting starts at 0). We store each label into ans at that athlete's original index.

Example: score = [10, 3, 8, 9, 4]. Sorting indices by score gives order [0, 3, 2, 4, 1]. So index 0 is Gold, index 3 is Silver, index 2 is Bronze, index 4 is "4", and index 1 is "5".

Writing labels back by original index is what lets the answer line up with the input order, even though we processed athletes in sorted order.

Time: O(n log n) Space: O(n)