506. Relative Ranks
Relative Ranks (LeetCode 506) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Top K Elements (Selection/Frequency) subpattern.
How to solve Relative Ranks
Relative Ranks is a Top K Elements problem, part of Heap (Priority Queue) Patterns. Find top K elements using heap. Solve kth largest, top K frequent, and k closest points problems.
Work towards the solution in these steps:
- Consider how you can determine the ranking order of the athletes based on their scores efficiently.
- Think about how sorting the scores or using a priority data structure can help you identify the top scores and their ranks.
- Since all scores are unique, how can you map each athlete's original position to their rank after sorting?
The reference solution runs in O(n log n) time and O(n) space.
The Relative Ranks solution and editorial walks through the full approach with reference code.
Problem statement
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.
The athletes are placed based on their scores, where the 1st place athlete has the highest score, the 2nd place athlete has the 2nd highest score, and so on. The placement of each athlete determines their rank:
- The 1st place athlete's rank is "Gold Medal".
- The 2nd place athlete's rank is "Silver Medal".
- The 3rd place athlete's rank is "Bronze Medal".
- For the 4th place to the nth place athlete, their rank is their placement number (i.e., the xth place athlete's rank is "x").
Return an array answer of size n where answer[i] is the rank of the ith athlete.
Example 1:
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].
Example 2:
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 <= 104
- 0 <= score[i] <= 106
- All the values in score are unique.
Topics and companies
Topics: Array, Sorting, Heap (Priority Queue).
Reported in interviews at Google.
How to practise Relative Ranks on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n) time and O(n) space.
Open Relative Ranks in the code editor, or read the Relative Ranks editorial for a worked solution with its approach and complexity analysis.
Where Relative Ranks sits in the DSA pattern sheet
- Heap (Priority Queue) Patterns pattern guide
- Top K Elements (Selection/Frequency) subpattern
- The full DSA patterns sheet
Problems related to Relative Ranks
Other problems that use the same Top K Elements (Selection/Frequency) and Heap (Priority Queue) Patterns techniques:
- K Closest Points to Origin — Medium, same subpattern
- Kth Largest Element in an Array — Medium, same subpattern
- Kth Largest Element in a Stream — Easy, same subpattern
- Last Stone Weight — Easy, same subpattern
- Sort Characters By Frequency — Medium, same subpattern
- Take Gifts From the Richest Pile — Easy, same subpattern
Relative Ranks FAQ
What is the LeetCode number of Relative Ranks?
Relative Ranks is LeetCode problem 506, rated Easy.
What pattern is used to solve Relative Ranks?
Relative Ranks is a Top K Elements problem. It belongs to the Heap (Priority Queue) Patterns pattern, in the Top K Elements (Selection/Frequency) subpattern.
What is the time complexity of Relative Ranks?
The reference solution runs in O(n log n) time and O(n) space.
Which companies ask Relative Ranks?
Relative Ranks has been reported in interviews at Google.