#506

Easy

LeetCode Problem Workspace

Relative Ranks

Solve Relative Ranks by sorting scores with original indices, then writing medal labels or numeric places back in answer order.

array sorting heap priority queue

Problem Statement

In Relative Ranks, each athlete has a unique score, and higher scores always produce better placements. After the competition is ranked from highest score to lowest score, the top three athletes receive special strings instead of numbers: "Gold Medal", "Silver Medal", and "Bronze Medal".

Your job is to build a result array aligned with the original score array, where each position stores that athlete's final rank label. For example, with score = [5,4,3,2,1], the sorted order is already clear, so the output becomes ["Gold Medal","Silver Medal","Bronze Medal","4","5"] because only the first three placements use medal names.

Examples

Example 1

Input: score = [5,4,3,2,1]

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

The placements are [1st, 2nd, 3rd, 4th, 5th].

Example 2

Input: score = [10,3,8,9,4]

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

The placements are [1st, 5th, 3rd, 2nd, 4th].

Constraints

n == score.length
1 <= n <= 104
0 <= score[i] <= 106
All the values in score are unique.

Solution Approach

Sort scores with original indices

The cleanest Array plus Sorting approach is to pair each score with its original index, then sort those pairs by score in descending order. This avoids losing where each athlete came from after sorting, which is the main failure mode in Relative Ranks.

Assign medals for the first three sorted positions

Walk the sorted pairs from best score to worst score. At sorted position 0, 1, and 2, write "Gold Medal", "Silver Medal", and "Bronze Medal" into the answer array at the original index. Starting from position 3, write the 1-based rank number as a string.

Alternative heap view for streaming top order

A max-heap can also pop athletes from highest score to lowest score while preserving original indices, which matches the Heap topic for this problem. It works well conceptually, but when all scores are already available, full sorting is usually simpler to code and easier to debug under interview time pressure.

Complexity Analysis

Metric	Value
Time	O(n + m)
Space	O(m)

If you use direct sorting on score-index pairs, the runtime is O(n log n) and the extra space is O(n) for the pairs and answer array. A bucket-style idea can reach O(n + m) time and O(m) space when score values stay within a manageable maximum range m, which matches the provided complexity seed, but most interview solutions for Relative Ranks use sorting because it is shorter and more robust.

What Interviewers Usually Probe

They want to see whether you preserve original indices after sorting descending scores.
They may ask why unique scores remove tie-handling logic from Relative Ranks.
They are checking whether you notice the output order is input order, not sorted order.

Common Pitfalls or Variants

Common pitfalls

Sorting the scores alone and forgetting which athlete each score belonged to.
Writing medal labels in sorted order and returning that sorted array instead of mapping back to original positions.
Using zero-based rank strings like "3" for the fourth athlete instead of converting placement to 1-based rank text.

Follow-up variants

Return only numeric ranks without medal strings, which removes the top-three special-case branch.
Handle duplicate scores, which changes Relative Ranks into a tie-ranking problem with shared placements.
Process athletes as they arrive, where a heap becomes more natural than one final sorting pass.

FAQ

What is the best approach for Relative Ranks?

The best default approach is to store each score with its original index, sort by score descending, and fill the answer array using medal strings for the top three placements and rank numbers for the rest.

Why does Relative Ranks need original indices?

After sorting, athletes move away from their input positions. You need the original indices so each computed rank label can be written back into the correct slot of the returned array.

Can I solve Relative Ranks with a heap instead of sorting?

Yes. A max-heap lets you repeatedly extract the next highest score and assign the next placement. That matches the problem's heap topic, but sorting is usually shorter and easier when the full array is given upfront.

What is the main Array plus Sorting pattern in this problem?

The pattern is sort transformed array entries while carrying enough metadata to rebuild the original layout. In Relative Ranks, that metadata is the athlete's original index.

Why are unique scores important in Relative Ranks?

Unique scores guarantee a strict ordering, so every athlete gets exactly one placement with no tie logic. That keeps the implementation focused on ranking order and output mapping rather than shared ranks.

terminal

Solution

Solution 1: Sorting

We use an array $\textit{idx}$ to store the indices from $0$ to $n-1$, then sort $\textit{idx}$ based on the values in $\textit{score}$ in descending order.

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        n = len(score)
        idx = list(range(n))
        idx.sort(key=lambda x: -score[x])
        top3 = ["Gold Medal", "Silver Medal", "Bronze Medal"]
        ans = [None] * n
        for i, j in enumerate(idx):
            ans[j] = top3[i] if i < 3 else str(i + 1)
        return ans

Continue Practicing

#502 ipo #621 task scheduler #630 course schedule iii