Relative Ranks solution and explanation
Google
9 more videos on this problem
Relative Ranks | 3 Approaches | Leetcode 506 | codestorywithMIKcodestorywithMIK · 30:39 · 5K views
506. Relative Ranks | LEETCODE EASYcode Explainer · 6:48 · 4K views
506. Relative Ranks (Leetcode Easy)Programming Live with Larry · 15:25 · 2K views
506. Relative Ranks | Sorting | Priority Queue | Multiset | Counting SortAryan Mittal · 16:01 · 2K views
LeetCode Problem 506 (EASY): Relative RanksAlex does LeetCode · 9:33 · 1K views
LeetCode#506 Relative Ranks - PythonCodeJulian · 1:01 · 878 views
Leetcode solving: 506. Relative RanksMath Geeks · 2:24 · 631 views
LeetCode 506 - Relative RanksSasi Kumar · 8:46 · 348 views
506. Relative Ranks (LeetCode, Java)hakunamatasq · 7:47 · 309 views
LeetCode 506 - Relative Ranks - JavaAlpha-Code · 11:05 · 292 views
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.
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
1stplace athlete's rank is"Gold Medal". - The
2ndplace athlete's rank is"Silver Medal". - The
3rdplace athlete's rank is"Bronze Medal". - For the
4thplace to thenthplace athlete, their rank is their placement number (i.e., thexthplace 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.length1 <= n <= 1040 <= score[i] <= 106- All the values in
scoreare unique.
Approach overview
Problem Overview: You are given an array of scores where each element represents an athlete’s score. The highest score gets "Gold Medal", the second highest gets "Silver Medal", the third gets "Bronze Medal", and the rest receive their numeric rank based on score order. The result must be returned in the same order as the original array.
Approach 1: Sorting with Index Mapping (O(n log n) time, O(n) space)
This approach sorts athletes by score while preserving their original positions. Create a list of pairs (score, index), then sort it in descending order using a standard sorting algorithm. After sorting, iterate through the list and assign ranks based on the sorted position: the first three positions map to medal strings and the rest get their rank number as a string. Use the stored indices to place the rank back into the correct position in the result array. The main cost comes from sorting, which takes O(n log n) time, while the additional array for storing pairs results in O(n) extra space.
Approach 2: HashMap to Determine Ranks (O(n log n) time, O(n) space)
This method separates ranking from result construction using a hash map. First, create a copy of the score array and sort it in descending order. Next, iterate through the sorted array and store each score’s rank in a HashMap where the key is the score and the value is its rank position. Once the ranking map is built, iterate through the original score array and look up each score’s rank in constant time. Convert the first three ranks to medal labels and keep numeric ranks for the rest. Hash lookups run in O(1) average time, so the overall complexity is dominated by sorting at O(n log n) with O(n) additional memory for the map. This approach highlights the use of arrays and hash-based lookups to simplify rank retrieval.
Both approaches rely on ordering scores globally. A heap (priority queue) could also track the highest scores incrementally, but sorting is simpler and usually faster in practice for this problem size.
Recommended for interviews: Sorting with index mapping is the expected solution. It clearly demonstrates how to maintain original positions while ranking sorted data. Interviewers typically accept the HashMap variant as well, but the index mapping approach is more direct and avoids an additional lookup structure. Showing the sorting strategy first demonstrates solid understanding of ranking problems and array manipulation.
Approach 1: Sorting with Index Mapping
The idea is to sort the scores but preserve their original indices by pairing each score with its index. Once sorted, we can easily determine their ranks by iterating over the sorted list. We then assign the corresponding rank values based on their positions (i.e., 'Gold Medal' for the first position, etc.). This approach utilizes additional space to maintain the original indices while sorting the scores.
def findRelativeRanks(score):
score_index = [(s, i) for i, s in enumerate(score)]
score_index.sort(reverse=True, key=lambda x: x[0])
n = len(score)
result = [''] * n
medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
for i, (s, idx) in enumerate(score_index):
if i < 3:
result[idx] = medals[i]
else:
result[idx] = str(i + 1)
return resultimport java.util.*;
public class Solution {
public String[] findRelativeRanks(int[] score) {
int n = score.length;
String[] result = new String[n];
String[] medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
int[][] scoreIndex = new int[n][2];
for (int i = 0; i < n; i++) {
scoreIndex[i][0] = score[i];
scoreIndex[i][1] = i;
}
Arrays.sort(scoreIndex, (a, b) -> b[0] - a[0]);
for (int i = 0; i < n; i++) {
if (i < 3) {
result[scoreIndex[i][1]] = medals[i];
} else {
result[scoreIndex[i][1]] = String.valueOf(i + 1);
}
}
return result;
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> findRelativeRanks(vector<int>& score) {
int n = score.size();
vector<pair<int, int>> scoreIndex;
for (int i = 0; i < n; ++i) {
scoreIndex.push_back({score[i], i});
}
sort(scoreIndex.rbegin(), scoreIndex.rend());
vector<string> result(n);
for (int i = 0; i < n; ++i) {
if (i == 0) result[scoreIndex[i].second] = "Gold Medal";
else if (i == 1) result[scoreIndex[i].second] = "Silver Medal";
else if (i == 2) result[scoreIndex[i].second] = "Bronze Medal";
else result[scoreIndex[i].second] = to_string(i + 1);
}
return result;
}var findRelativeRanks = function(score) {
let scoreIndex = score.map((s, i) => [s, i]);
scoreIndex.sort((a, b) => b[0] - a[0]);
const medals = ["Gold Medal", "Silver Medal", "Bronze Medal"];
let result = new Array(score.length);
for (let i = 0; i < scoreIndex.length; i++) {
if (i < 3) {
result[scoreIndex[i][1]] = medals[i];
} else {
result[scoreIndex[i][1]] = (i + 1).toString();
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct ScoreIndex {
int score;
int index;
};
int compare(const void *a, const void *b) {
return ((struct ScoreIndex*)b)->score - ((struct ScoreIndex*)a)->score;
}
char **findRelativeRanks(int* score, int scoreSize, int* returnSize) {
struct ScoreIndex scoreIndex[scoreSize];
char **result = (char **)malloc(scoreSize * sizeof(char *));
const char *medals[] = {"Gold Medal", "Silver Medal", "Bronze Medal"};
for (int i = 0; i < scoreSize; i++) {
scoreIndex[i].score = score[i];
scoreIndex[i].index = i;
}
qsort(scoreIndex, scoreSize, sizeof(struct ScoreIndex), compare);
for (int i = 0; i < scoreSize; i++) {
if (i < 3) {
result[scoreIndex[i].index] = strdup(medals[i]);
} else {
result[scoreIndex[i].index] = (char *)malloc(10 * sizeof(char));
sprintf(result[scoreIndex[i].index], "%d", i + 1);
}
}
*returnSize = scoreSize;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public string[] FindRelativeRanks(int[] score) {
int n = score.Length;
List<Tuple<int, int>> scoreIndex = new List<Tuple<int, int>>();
for (int i = 0; i < n; i++) {
scoreIndex.Add(new Tuple<int, int>(score[i], i));
}
scoreIndex.Sort((a, b) => b.Item1.CompareTo(a.Item1));
string[] result = new string[n];
string[] medals = { "Gold Medal", "Silver Medal", "Bronze Medal" };
for (int i = 0; i < n; i++) {
if (i < 3) {
result[scoreIndex[i].Item2] = medals[i];
} else {
result[scoreIndex[i].Item2] = (i + 1).ToString();
}
}
return result;
}
}Python uses list comprehension to pair scores with their indices and sorts this list in descending order. We use enumerate while sorting to easily track original indices. After sorting, ranks are assigned based on sorted positions with appropriate conversion for top three scores.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing the score-index pairs and the result list.
Approach 2: HashMap to Determine Ranks
In this approach, we employ a hash map (or dictionary) to map each score to its ranking position in a sorted list. The scores are first sorted to determine order-based ranks. We then iterate through original scores, using the map to quickly assign the appropriate ranking (medal or numeric) to each score.
def findRelativeRanks(score):
sorted_scores = sorted(score, reverse=True)
rank_map = {v: str(i+1) for i, v in enumerate(sorted_scores)}
medals = {0: 'Gold Medal', 1: 'Silver Medal', 2: 'Bronze Medal'}
return [medals.get(int(rank_map[s]) - 1, rank_map[s]) for s in score]import java.util.*;
public class Solution {
public String[] findRelativeRanks(int[] score) {
Integer[] sortedScores = Arrays.stream(score).boxed().toArray(Integer[]::new);
Map<Integer, Integer> rankMap = new HashMap<>();
Arrays.sort(sortedScores, Collections.reverseOrder());
for (int i = 0; i < sortedScores.length; i++) {
rankMap.put(sortedScores[i], i);
}
String[] result = new String[score.length];
String[] medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
for (int i = 0; i < score.length; i++) {
int rank = rankMap.get(score[i]);
if (rank < 3) {
result[i] = medals[rank];
} else {
result[i] = String.valueOf(rank + 1);
}
}
return result;
}
}#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<string> findRelativeRanks(vector<int>& score) {
vector<int> sortedScores = score;
unordered_map<int, int> rankMap;
sort(sortedScores.rbegin(), sortedScores.rend());
for (int i = 0; i < sortedScores.size(); ++i) {
rankMap[sortedScores[i]] = i;
}
vector<string> result(score.size());
string medals[] = {"Gold Medal", "Silver Medal", "Bronze Medal"};
for (int i = 0; i < score.size(); ++i) {
int rank = rankMap[score[i]];
if (rank < 3) {
result[i] = medals[rank];
} else {
result[i] = to_string(rank + 1);
}
}
return result;
}var findRelativeRanks = function(score) {
let sortedScores = [...score].sort((a, b) => b - a);
let rankMap = new Map();
sortedScores.forEach((val, index) => {
rankMap.set(val, index);
});
const medals = ["Gold Medal", "Silver Medal", "Bronze Medal"];
return score.map(s => {
const rank = rankMap.get(s);
return rank < 3 ? medals[rank] : (rank + 1).toString();
});
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmpfunc(const void *a, const void *b) {
return (*(int*)b - *(int*)a);
}
char** findRelativeRanks(int* score, int scoreSize, int* returnSize) {
int *sorted = (int*)malloc(scoreSize * sizeof(int));
memcpy(sorted, score, scoreSize * sizeof(int));
qsort(sorted, scoreSize, sizeof(int), cmpfunc);
char **result = (char**)malloc(scoreSize * sizeof(char*));
const char *medals[] = {"Gold Medal", "Silver Medal", "Bronze Medal"};
for (int i = 0; i < scoreSize; i++) {
int rank = (int)(strchr(sorted, score[i]) - sorted);
if (rank < 3) {
result[i] = strdup(medals[rank]);
} else {
result[i] = (char *)malloc(10 * sizeof(char));
sprintf(result[i], "%d", rank + 1);
}
}
free(sorted);
*returnSize = scoreSize;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public string[] FindRelativeRanks(int[] score) {
int[] sortedScores = new int[score.Length];
Array.Copy(score, sortedScores, score.Length);
Array.Sort(sortedScores, (a, b) => b.CompareTo(a));
Dictionary<int, int> rankMap = new Dictionary<int, int>();
for (int i = 0; i < sortedScores.Length; i++) {
rankMap[sortedScores[i]] = i;
}
string[] result = new string[score.Length];
string[] medals = { "Gold Medal", "Silver Medal", "Bronze Medal" };
for (int i = 0; i < score.Length; i++) {
int rank = rankMap[score[i]];
result[i] = rank < 3 ? medals[rank] : (rank + 1).ToString();
}
return result;
}
}This Python solution builds a mapping of each score to its ranking position from a sorted list of scores. Using a dictionary, ranks are quickly accessed and converted to medals where appropriate. This method effectively isolates rank determination from subsequent placement in the result.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) due to dictionary for rank mapping.
Approach 3: Sorting
We use an array idx to store the indices from 0 to n-1, then sort idx based on the values in score in descending order.
Next, we define an array top3 = [Gold Medal, Silver Medal, Bronze Medal]. We traverse idx, and for each index j, if j is less than 3, then ans[j] is top3[j]; otherwise, it is j+1.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array score.
function findRelativeRanks(score: number[]): string[] {
const n = score.length;
const idx = Array.from({ length: n }, (_, i) => i);
idx.sort((a, b) => score[b] - score[a]);
const top3 = ['Gold Medal', 'Silver Medal', 'Bronze Medal'];
const ans: string[] = Array(n);
for (let i = 0; i < n; i++) {
if (i < 3) {
ans[idx[i]] = top3[i];
} else {
ans[idx[i]] = (i + 1).toString();
}
}
return ans;
}func findRelativeRanks(score []int) []string {
n := len(score)
idx := make([][]int, n)
for i := 0; i < n; i++ {
idx[i] = []int{score[i], i}
}
sort.Slice(idx, func(i1, i2 int) bool {
return idx[i1][0] > idx[i2][0]
})
ans := make([]string, n)
top3 := []string{"Gold Medal", "Silver Medal", "Bronze Medal"}
for i := 0; i < n; i++ {
if i < 3 {
ans[idx[i][1]] = top3[i]
} else {
ans[idx[i][1]] = strconv.Itoa(i + 1)
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting with Index Mapping | Time Complexity: O(n log n) due to sorting. |
| HashMap to Determine Ranks | Time Complexity: O(n log n) due to sorting. |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting with Index Mapping | O(n log n) | O(n) | General solution when you need to rank values but keep original indices |
| HashMap to Determine Ranks | O(n log n) | O(n) | Useful when separating rank computation from final result lookup |
Frequently asked questions
Is Relative Ranks easy or hard?
Relative Ranks is classified as an Easy problem on LeetCode. The challenge mainly involves sorting scores and maintaining original indices while assigning ranks. Developers comfortable with array manipulation and sorting can implement the solution quickly.
Relative Ranks Python/Java solution
Python and Java implementations typically sort score-index pairs or use a map from score to rank. After sorting in descending order, assign 'Gold Medal', 'Silver Medal', 'Bronze Medal', and numeric ranks for the rest, then place them in the result array according to original indices.
How to solve Relative Ranks in O(n)?
Pure O(n) solutions are difficult because ranking requires comparing all scores globally. Most implementations rely on sorting which costs O(n log n). A bucket-based approach could achieve near O(n) if the score range is small, but that assumption is not guaranteed in the problem constraints.
What is the best approach for Relative Ranks?
Sorting with index mapping is the most common and clean solution. Pair each score with its original index, sort the pairs in descending order, and assign ranks while writing results back to the correct positions. This approach runs in O(n log n) time due to sorting and uses O(n) additional space.
Is Relative Ranks asked at Google/Amazon/Meta?
Relative Ranks appears frequently in coding practice sets and interview preparation platforms. Variations of ranking and sorting problems are commonly asked by companies like Amazon and Google to evaluate understanding of arrays, sorting, and index tracking.
What data structure is used in Relative Ranks?
Arrays are used to store scores and results, while additional structures like pairs or hash maps help track ranks. Some implementations also use heaps (priority queues) to repeatedly extract the highest score, though sorting is usually simpler.
What is the time complexity of Relative Ranks?
The standard solution runs in O(n log n) time because the scores must be sorted to determine ranking order. After sorting, assigning ranks and building the result array takes O(n). Space complexity is typically O(n) for storing indices or rank mappings.