Relative Ranks Python Solution with Tests

LeetCode 506, Easy. Topics: Array, Sorting, Heap (Priority Queue). View on LeetCode. Generate this problem as a practice environment: tested reference solution, 16 parametrized pytest cases, and a playground notebook:

lcpy gen -n 506   # by problem number
lcpy gen -s relative_ranks   # by problem name

Problem

You are given an integer array score of size n, where score[i] is the score of the i^th athlete in a competition. All the scores are guaranteed to be unique. The athletes are placed based on their scores, where the 1^st place athlete has the highest score, the 2^nd place athlete has the 2^nd highest score, and so on. The placement of each athlete determines their rank:

The 1^st place athlete’s rank is "Gold Medal".
The 2^nd place athlete’s rank is "Silver Medal".
The 3^rd place athlete’s rank is "Bronze Medal".
For the 4^th place to the n^th place athlete, their rank is their placement number (i.e., the x^th place athlete’s rank is "x").

Return an array answer of size n where answer[i] is the rank of the i^th athlete.

Examples

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

Input: score = [10,3,8,9,4]
Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
Explanation: The placements are [1st, 5th, 3rd, 2nd, 4th].

Constraints

n == score.length
1 <= n <= 10^4
0 <= score[i] <= 10^6
All the values in score are unique.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n log n) for the descending sort over n scores
    # Space: O(n) for the placement order and the rank output
    def find_relative_ranks(self, score: list[int]) -> list[str]:
        medals = ("Gold Medal", "Silver Medal", "Bronze Medal")
        order = sorted(range(len(score)), key=score.__getitem__, reverse=True)
        ranks = [""] * len(score)
        for place, idx in enumerate(order):
            ranks[idx] = medals[place] if place < 3 else str(place + 1)
        return ranks

Complexity

Time	Space
O(n log n) for the descending sort over n scores	O(n) for the placement order and the rank output

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Relative Ranks Python Solution with Tests

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags