Relative Ranks

Problem

Given scores, assign ranks: "Gold Medal" for 1st, "Silver Medal" for 2nd, "Bronze Medal" for 3rd, then "4", "5", etc.

Key insight: Sort indices by score descending, assign ranks by position.

Solutions

# Python
def findRelativeRanks(score):
    medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
    ranked = sorted(range(len(score)), key=lambda i: -score[i])
    result = [''] * len(score)
    for i, idx in enumerate(ranked):
        result[idx] = medals[i] if i < 3 else str(i + 1)
    return result

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

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

// JavaScript
function findRelativeRanks(score) {
    const medals = ["Gold Medal", "Silver Medal", "Bronze Medal"];
    const ranked = [...score.keys()].sort((a, b) => score[b] - score[a]);
    const result = Array(score.length);
    ranked.forEach((idx, i) => result[idx] = i < 3 ? medals[i] : String(i + 1));
    return result;
}

Complexity

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