# LeetCode 506: Relative Ranks

## Problem Restatement

We are given an integer array `score`.

`score[i]` is the score of the `i`th athlete.

All scores are unique.

Athletes are ranked from highest score to lowest score:

| Place | Rank string |
|---|---|
| 1st | `"Gold Medal"` |
| 2nd | `"Silver Medal"` |
| 3rd | `"Bronze Medal"` |
| 4th and later | The placement number as a string |

We need to return an array `answer` where:

```python
answer[i]
```

is the rank of the `i`th athlete in the original input order.

The official problem states that all scores are unique and asks us to return each athlete's rank based on descending score order.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `score` |
| Output | A string array `answer` |
| `answer[i]` | Rank of athlete `i` |
| Ranking rule | Higher score means better rank |

Function shape:

```python
class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        ...
```

## Examples

Example 1:

```python
score = [5, 4, 3, 2, 1]
```

The scores are already in descending order.

So the placements are:

| Athlete index | Score | Place | Rank |
|---|---:|---:|---|
| 0 | 5 | 1 | `"Gold Medal"` |
| 1 | 4 | 2 | `"Silver Medal"` |
| 2 | 3 | 3 | `"Bronze Medal"` |
| 3 | 2 | 4 | `"4"` |
| 4 | 1 | 5 | `"5"` |

The answer is:

```python
["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
```

Example 2:

```python
score = [10, 3, 8, 9, 4]
```

Sort scores from highest to lowest:

```text
10, 9, 8, 4, 3
```

So:

| Score | Original index | Place | Rank |
|---:|---:|---:|---|
| 10 | 0 | 1 | `"Gold Medal"` |
| 9 | 3 | 2 | `"Silver Medal"` |
| 8 | 2 | 3 | `"Bronze Medal"` |
| 4 | 4 | 4 | `"4"` |
| 3 | 1 | 5 | `"5"` |

Put ranks back into original index order:

```python
["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]
```

## First Thought: Sort the Scores

The ranking comes from sorting scores in descending order.

However, if we sort only the values, we lose the original athlete positions.

For example:

```python
score = [10, 3, 8, 9, 4]
```

After sorting:

```python
[10, 9, 8, 4, 3]
```

we know the rank order, but we still need to place each rank back into the answer array using the original index.

So we need to remember where each score came from.

## Key Insight

Sort the indices instead of sorting only the scores.

Create:

```python
indices = [0, 1, 2, ..., n - 1]
```

Then sort those indices by their corresponding scores:

```python
indices.sort(key=lambda i: score[i], reverse=True)
```

After sorting:

```python
indices[0]
```

is the original index of the highest-scoring athlete.

```python
indices[1]
```

is the original index of the second-highest-scoring athlete.

Then we can assign ranks directly into the correct answer positions.

## Algorithm

Let `n = len(score)`.

Create an answer array:

```python
answer = [""] * n
```

Create indices:

```python
indices = list(range(n))
```

Sort them by descending score.

Then scan the sorted indices.

For position `place_index` and original index `athlete_index`:

1. If `place_index == 0`, assign `"Gold Medal"`.
2. If `place_index == 1`, assign `"Silver Medal"`.
3. If `place_index == 2`, assign `"Bronze Medal"`.
4. Otherwise, assign `str(place_index + 1)`.

The `+ 1` is needed because array positions are zero-based, but ranks start at `1`.

## Correctness

Sorting the indices by `score[i]` in descending order places the athletes from highest score to lowest score.

Because all scores are unique, every athlete has a distinct placement.

For every sorted position `place_index`, the athlete at `indices[place_index]` has placement `place_index + 1`.

The algorithm assigns the correct medal string for placements `1`, `2`, and `3`.

For every placement from `4` onward, it assigns the placement number as a string.

Each rank is written to `answer[athlete_index]`, so the final array preserves the original athlete order.

Therefore, `answer[i]` is exactly the rank of the `i`th athlete.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting the indices dominates |
| Space | `O(n)` | The answer array and index array both have length `n` |

## Implementation

```python
from typing import List

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        n = len(score)
        answer = [""] * n

        indices = list(range(n))
        indices.sort(key=lambda i: score[i], reverse=True)

        medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]

        for place_index, athlete_index in enumerate(indices):
            if place_index < 3:
                answer[athlete_index] = medals[place_index]
            else:
                answer[athlete_index] = str(place_index + 1)

        return answer
```

## Code Explanation

Create the result array:

```python
answer = [""] * n
```

This will store ranks in the original athlete order.

Create the list of original indices:

```python
indices = list(range(n))
```

Sort indices by score descending:

```python
indices.sort(key=lambda i: score[i], reverse=True)
```

The medal names are stored in order:

```python
medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
```

Now each position in `indices` tells us a placement:

```python
for place_index, athlete_index in enumerate(indices):
```

If the athlete is in the top three, assign the medal:

```python
answer[athlete_index] = medals[place_index]
```

Otherwise, assign the numeric rank:

```python
answer[athlete_index] = str(place_index + 1)
```

Finally, return the answer.

## Testing

```python
def test_find_relative_ranks():
    s = Solution()

    assert s.findRelativeRanks([5, 4, 3, 2, 1]) == [
        "Gold Medal",
        "Silver Medal",
        "Bronze Medal",
        "4",
        "5",
    ]

    assert s.findRelativeRanks([10, 3, 8, 9, 4]) == [
        "Gold Medal",
        "5",
        "Bronze Medal",
        "Silver Medal",
        "4",
    ]

    assert s.findRelativeRanks([1]) == ["Gold Medal"]

    assert s.findRelativeRanks([2, 1]) == [
        "Gold Medal",
        "Silver Medal",
    ]

    assert s.findRelativeRanks([1, 100, 50]) == [
        "Bronze Medal",
        "Gold Medal",
        "Silver Medal",
    ]

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| Already sorted scores | Checks direct ranking |
| Unsorted scores | Checks original index restoration |
| One athlete | Only gold medal exists |
| Two athletes | Only gold and silver are used |
| Three athletes | All medal ranks are used |