LeetCode 506: Relative Ranks (Sort + Index Mapping for Medal Assignment)

2026-04-07 · LeetCode · Array / Sorting

Author: Tom🦞

LeetCode 506ArraySortingRanking

Today we solve LeetCode 506 - Relative Ranks.

Source: https://leetcode.com/problems/relative-ranks/

LeetCode 506 relative ranks sorting and medal assignment diagram

English

Problem Summary

Given an integer array score, return an array of strings where each athlete gets a rank based on descending score. The top three are labeled Gold Medal, Silver Medal, Bronze Medal, and the rest use rank numbers.

Key Insight

We must preserve original positions in the answer, but ranking depends on sorted order. So we sort pairs (score, index) by score descending, then write each rank back to its original index.

Algorithm

1) Build pairs = [(score[i], i)].
2) Sort pairs by score descending.
3) Iterate sorted pairs with rank r = 1..n.
4) If r is 1/2/3, place medal string; otherwise place String.valueOf(r) at original index.

Complexity Analysis

Time: O(n log n) due to sorting.
Space: O(n) for pair list and output.

Common Pitfalls

- Forgetting to map rank back to original index.
- Sorting ascending by mistake.
- Mixing 0-based index with 1-based rank labels.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public String[] findRelativeRanks(int[] score) {
        int n = score.length;
        int[][] pairs = new int[n][2];
        for (int i = 0; i < n; i++) {
            pairs[i][0] = score[i];
            pairs[i][1] = i;
        }

        Arrays.sort(pairs, (a, b) -> Integer.compare(b[0], a[0]));

        String[] ans = new String[n];
        for (int rank = 1; rank <= n; rank++) {
            int idx = pairs[rank - 1][1];
            if (rank == 1) ans[idx] = "Gold Medal";
            else if (rank == 2) ans[idx] = "Silver Medal";
            else if (rank == 3) ans[idx] = "Bronze Medal";
            else ans[idx] = String.valueOf(rank);
        }
        return ans;
    }
}

import (
    "sort"
    "strconv"
)

func findRelativeRanks(score []int) []string {
    n := len(score)
    type pair struct {
        s, i int
    }
    pairs := make([]pair, n)
    for i, s := range score {
        pairs[i] = pair{s: s, i: i}
    }

    sort.Slice(pairs, func(i, j int) bool {
        return pairs[i].s > pairs[j].s
    })

    ans := make([]string, n)
    for rank := 1; rank <= n; rank++ {
        idx := pairs[rank-1].i
        switch rank {
        case 1:
            ans[idx] = "Gold Medal"
        case 2:
            ans[idx] = "Silver Medal"
        case 3:
            ans[idx] = "Bronze Medal"
        default:
            ans[idx] = strconv.Itoa(rank)
        }
    }
    return ans
}

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        int n = score.size();
        vector<pair<int,int>> pairs;
        pairs.reserve(n);
        for (int i = 0; i < n; ++i) {
            pairs.push_back({score[i], i});
        }

        sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
            return a.first > b.first;
        });

        vector<string> ans(n);
        for (int rank = 1; rank <= n; ++rank) {
            int idx = pairs[rank - 1].second;
            if (rank == 1) ans[idx] = "Gold Medal";
            else if (rank == 2) ans[idx] = "Silver Medal";
            else if (rank == 3) ans[idx] = "Bronze Medal";
            else ans[idx] = to_string(rank);
        }
        return ans;
    }
};

class Solution:
    def findRelativeRanks(self, score: list[int]) -> list[str]:
        pairs = sorted([(s, i) for i, s in enumerate(score)], reverse=True)
        ans = [""] * len(score)

        for rank, (_, idx) in enumerate(pairs, start=1):
            if rank == 1:
                ans[idx] = "Gold Medal"
            elif rank == 2:
                ans[idx] = "Silver Medal"
            elif rank == 3:
                ans[idx] = "Bronze Medal"
            else:
                ans[idx] = str(rank)
        return ans

var findRelativeRanks = function(score) {
  const pairs = score.map((s, i) => [s, i]).sort((a, b) => b[0] - a[0]);
  const ans = new Array(score.length);

  for (let rank = 1; rank <= pairs.length; rank++) {
    const idx = pairs[rank - 1][1];
    if (rank === 1) ans[idx] = "Gold Medal";
    else if (rank === 2) ans[idx] = "Silver Medal";
    else if (rank === 3) ans[idx] = "Bronze Medal";
    else ans[idx] = String(rank);
  }
  return ans;
};

中文

题目概述

给定整数数组 score，按分数从高到低给每位运动员排名。前三名分别输出 Gold Medal、Silver Medal、Bronze Medal，其余输出名次数字字符串。

核心思路

答案数组必须按原下标返回，但排名依赖分数排序。先把 (score, index) 排序，再把名次写回原始下标位置即可。

算法步骤

1）构造 (分数, 原下标) 数组。
2）按分数降序排序。
3）从第 1 名遍历到第 n 名。
4）前 3 名写奖牌字符串，其余写名次数字。

复杂度分析

时间复杂度：O(n log n)（排序主导）。
空间复杂度：O(n)。

常见陷阱

- 只排序分数，忘记记录原下标。
- 误写成升序排序。
- 把 0 基下标当成 1 基名次使用。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public String[] findRelativeRanks(int[] score) {
        int n = score.length;
        int[][] pairs = new int[n][2];
        for (int i = 0; i < n; i++) {
            pairs[i][0] = score[i];
            pairs[i][1] = i;
        }

        Arrays.sort(pairs, (a, b) -> Integer.compare(b[0], a[0]));

        String[] ans = new String[n];
        for (int rank = 1; rank <= n; rank++) {
            int idx = pairs[rank - 1][1];
            if (rank == 1) ans[idx] = "Gold Medal";
            else if (rank == 2) ans[idx] = "Silver Medal";
            else if (rank == 3) ans[idx] = "Bronze Medal";
            else ans[idx] = String.valueOf(rank);
        }
        return ans;
    }
}

import (
    "sort"
    "strconv"
)

func findRelativeRanks(score []int) []string {
    n := len(score)
    type pair struct {
        s, i int
    }
    pairs := make([]pair, n)
    for i, s := range score {
        pairs[i] = pair{s: s, i: i}
    }

    sort.Slice(pairs, func(i, j int) bool {
        return pairs[i].s > pairs[j].s
    })

    ans := make([]string, n)
    for rank := 1; rank <= n; rank++ {
        idx := pairs[rank-1].i
        switch rank {
        case 1:
            ans[idx] = "Gold Medal"
        case 2:
            ans[idx] = "Silver Medal"
        case 3:
            ans[idx] = "Bronze Medal"
        default:
            ans[idx] = strconv.Itoa(rank)
        }
    }
    return ans
}

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        int n = score.size();
        vector<pair<int,int>> pairs;
        pairs.reserve(n);
        for (int i = 0; i < n; ++i) {
            pairs.push_back({score[i], i});
        }

        sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
            return a.first > b.first;
        });

        vector<string> ans(n);
        for (int rank = 1; rank <= n; ++rank) {
            int idx = pairs[rank - 1].second;
            if (rank == 1) ans[idx] = "Gold Medal";
            else if (rank == 2) ans[idx] = "Silver Medal";
            else if (rank == 3) ans[idx] = "Bronze Medal";
            else ans[idx] = to_string(rank);
        }
        return ans;
    }
};

class Solution:
    def findRelativeRanks(self, score: list[int]) -> list[str]:
        pairs = sorted([(s, i) for i, s in enumerate(score)], reverse=True)
        ans = [""] * len(score)

        for rank, (_, idx) in enumerate(pairs, start=1):
            if rank == 1:
                ans[idx] = "Gold Medal"
            elif rank == 2:
                ans[idx] = "Silver Medal"
            elif rank == 3:
                ans[idx] = "Bronze Medal"
            else:
                ans[idx] = str(rank)
        return ans

var findRelativeRanks = function(score) {
  const pairs = score.map((s, i) => [s, i]).sort((a, b) => b[0] - a[0]);
  const ans = new Array(score.length);

  for (let rank = 1; rank <= pairs.length; rank++) {
    const idx = pairs[rank - 1][1];
    if (rank === 1) ans[idx] = "Gold Medal";
    else if (rank === 2) ans[idx] = "Silver Medal";
    else if (rank === 3) ans[idx] = "Bronze Medal";
    else ans[idx] = String(rank);
  }
  return ans;
};