EasyNo. 0506
Relative Ranks — LeetCode 506 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Sorting, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an integer array score of size n, where score[i] is the score of the ith athlete in a competition. All the scores are guaranteed to be unique.
Example
- 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].
Python solution
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 ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 506. Relative Ranks is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0215 | Kth Largest Element in an Array | Medium |
| 0218 | The Skyline Problem | Hard |
| 0912 | Sort an Array | Medium |
| 0973 | K Closest Points to Origin | Medium |
| 1094 | Car Pooling | Medium |
| 1424 | Diagonal Traverse II | Medium |
Frequently asked questions
- How hard is LeetCode 506. Relative Ranks?
LeetCode 506. Relative Ranks is rated Easy on LeetCode.
- What is the time complexity of LeetCode 506. Relative Ranks?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 506. Relative Ranks?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 506. Relative Ranks cover?
LeetCode 506. Relative Ranks is tagged Array, Sorting and Heap (Priority Queue) on LeetCode.