506. Relative Ranks

Problem Description

You are given a list of scores for athletes in a competition. Each score in the score array is unique, and represents the score of an athlete, where score[i] is the score for the ith athlete. The goal is to rank the athletes based on their scores in descending order — the highest score gets the first rank, the second-highest gets the second rank, and so forth.

For the top three ranks, specific strings are used instead of numbers:

The 1st place is given the rank "Gold Medal".
The 2nd place is given the rank "Silver Medal".
The 3rd place is given the rank "Bronze Medal".

For all other positions starting from the 4th to the nth place, the rank is the numeric place of the athlete in the sorted list. The task is to return an array where each element represents the rank of the corresponding athlete in the original input array.

Intuition

The problem can be simplified to sorting the athletes based on their scores and then assigning ranks according to their sorted positions. Since we are interested in the order of scores and need to remember the original indices, we can sort the indexes of the athletes based on the scores they map to. We perform the sort in descending order to ensure that the athlete with the highest score gets the first index.

Once we have the indices sorted by the athletes' scores, we can map these to their respective ranks. For the first three athletes (indices 0, 1, and 2) after sorting, we assign the special ranks ("Gold Medal", "Silver Medal", "Bronze Medal"). For all other athletes, we convert their index position (plus one, since we rank starting from 1 not 0) to a string to represent their numeric rank. The reason we add 1 is that ranks are typically 1-indexed, not 0-indexed. Finally, we place these rank strings in a new array ans with the same size as the input array, ensuring that each athlete's rank is placed in their original index in the input array.

Learn more about Sorting and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Solution Approach

The provided Python code implements a solution that carefully maps the athletes' scores to their respective ranks. Here's how the code works in detail, breaking it down into key steps:

First, we calculate the length of the input score array, which represents the number of athletes. This is stored in the variable n.
We then create a list called idx, which is a list of indices from 0 to n-1. These indexes correspond to the positions of athletes in the score array.
The idx list is sorted using a custom key function which sorts the indexes based on the scores at those indexes in descending order. The lambda function lambda x: -score[x] returns the negative score value for each index, thus ensuring a descending sort.
A top3 list is defined with the strings "Gold Medal", "Silver Medal", and "Bronze Medal" which are the ranks for the top three athletes.
We create an array ans initialized with None values, with the same length as the number of athletes. This will be used to store the final rankings.
A loop runs from 0 to n to assign ranks to all athletes. The current index in the sorted idx list determines the athlete's placement in the sorted order.
Inside the loop:
- If the index is less than 3 (meaning the athlete is in the top three), we use the top3 list to assign "Gold Medal", "Silver Medal", or "Bronze Medal" accordingly.
- For all other indices (4th place and beyond), we convert the index to a string, while also adding 1 to it to account for the fact that rankings start from 1 instead of 0. This string is the athlete's rank.
We assign these ranks to the corresponding positions in the ans array based on the sorted indices. This ensures each athlete's rank is placed at the same index as they originally appeared in the score array.
Finally, the ans array, now filled with the rankings, is returned.

This approach ensures that the athletes are ranked according to their scores, with the original array structure preserved, and special rankings are given to the top three athletes.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Example Walkthrough

Let’s walk through a small example to illustrate the solution approach described in the content above. Suppose we have the following list of scores for a competition:

1scores = [50, 30, 80, 70, 10]

We want to determine the ranks of these athletes, with the top three receiving "Gold Medal", "Silver Medal", and "Bronze Medal", respectively.

The detailed steps would be:

Calculate the length of the scores array, n = 5.
Create a list of indices idx = [0, 1, 2, 3, 4].
Sort the idx list by the athletes' scores in descending order:

You will end up with indices sorted as [2, 3, 0, 1, 4] because when mapping these indices back to the scores, you get [80, 70, 50, 30, 10] which is in descending order.
Define a list top3 = ["Gold Medal", "Silver Medal", "Bronze Medal"].
Initialize an array ans = [None, None, None, None, None] to store the rankings.
Loop through indices in idx and assign ranks as follows:
- At idx[0] (which is 2), the score is 80. Since it is the highest, assign "Gold Medal" to ans[2].
- At idx[1] (which is 3), the score is 70. Assign "Silver Medal" to ans[3].
- At idx[2] (which is 0), the score is 50. Assign "Bronze Medal" to ans[0].
- At idx[3] (which is 1), the score is 30. This is the 4th highest score, so assign the string '4' to ans[1].
- At idx[4] (which is 4), the score is 10. This is the 5th highest score, so assign the string '5' to ans[4].
The iteration assigns ranks based on the sorted indices and maps them back to the original ans array at their respective positions.
Final ans array after the loop will be:

1ans = ["Bronze Medal", "4", "Gold Medal", "Silver Medal", "5"]

As shown in the ans array, we have assigned the correct rank to each athlete based on their original position in the scores array. Athlete with score 80 (3rd in the original array) gets "Gold Medal", athlete with score 70 (4th in the original array) gets "Silver Medal", and so on.

The final output correctly represents the ranks of the athletes corresponding to their scores in descending order, fulfilling the problem description.

Solution Implementation

1class Solution:
2    def find_relative_ranks(self, scores: List[int]) -> List[str]:
3        # Find the number of scores
4        num_scores = len(scores)
5      
6        # Create a list of indices from the scores list
7        indices = list(range(num_scores))
8      
9        # Sort indices based on the scores in descending order
10        indices.sort(key=lambda x: -scores[x])
11      
12        # Define strings for the top three positions
13        top_three_medals = ['Gold Medal', 'Silver Medal', 'Bronze Medal']
14      
15        # Initialize the answer list with placeholders
16        answer = [None] * num_scores
17      
18        # Fill the answer list with the appropriate rank strings
19        for rank, index in enumerate(indices):
20            # If the rank is less than 3, assign a medal string
21            if rank < 3:
22                answer[index] = top_three_medals[rank]
23            else:
24                # Otherwise, assign the numeric rank as a string
25                answer[index] = str(rank + 1)
26      
27        # Return the completed answer list with ranks
28        return answer
29

1class Solution {
2
3    // Method to find the relative ranks for athletes based on their scores.
4    public String[] findRelativeRanks(int[] scores) {
5        // Get the number of athletes based on the length of scores array.
6        int numAthletes = scores.length;
7      
8        // Create a wrapper array to hold the indices of the scores. 
9        Integer[] indices = new Integer[numAthletes];
10      
11        // Initialize the indices array with values from 0 to numAthletes-1.
12        for (int i = 0; i < numAthletes; ++i) {
13            indices[i] = i;
14        }
15      
16        // Sort the indices array based on the scores in descending order. 
17        // The comparison function uses the scores at the indices to sort the indices.
18        Arrays.sort(indices, (a, b) -> Integer.compare(scores[b], scores[a]));
19      
20        // Create an array to hold the answers (relative ranks as strings).
21        String[] ranks = new String[numAthletes];
22      
23        // Create an array to hold the medals for the top 3 athletes.
24        String[] medals = new String[] {"Gold Medal", "Silver Medal", "Bronze Medal"};
25      
26        // Assign the appropriate rank to each athlete in the ranks array.
27        for (int i = 0; i < numAthletes; ++i) {
28            // If the rank is within the top 3, assign the corresponding medal.
29            if (i < 3) {
30                ranks[indices[i]] = medals[i];
31            } else {
32                // Otherwise, assign the rank number as a string (1-indexed).
33                ranks[indices[i]] = String.valueOf(i + 1);
34            }
35        }
36      
37        // Return the array of ranks.
38        return ranks;
39    }
40}
41

1#include <vector>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9    // This method finds and returns the relative ranks of athletes based on their scores.
10    vector<string> findRelativeRanks(vector<int>& scores) {
11        int numOfScores = scores.size();
12
13        // Use a vector of pairs to keep track of the scores and their original indices.
14        vector<pair<int, int>> indexedScores;
15        for (int i = 0; i < numOfScores; ++i) {
16            indexedScores.push_back(make_pair(scores[i], i));
17        }
18
19        // Sort the indexed scores in descending order using a custom comparator lambda function.
20        sort(indexedScores.begin(), indexedScores.end(),
21            [](const pair<int, int>& a, const pair<int, int>& b) { return a.first > b.first; });
22
23        // Initialize the answer vector with the same size as the number of scores.
24        vector<string> ranks(numOfScores);
25
26        // Define medals for the top 3 scores.
27        vector<string> medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
28
29        // Assign ranks to the athletes based on sorted order.
30        for (int i = 0; i < numOfScores; ++i) {
31            if (i < 3) {
32                // Assign medals to the top 3 scores.
33                ranks[indexedScores[i].second] = medals[i];
34            } else {
35                // For others, assign the rank as a string (1-indexed).
36                ranks[indexedScores[i].second] = to_string(i + 1);
37            }
38        }
39
40        return ranks;
41    }
42};
43

1// Import the necessary functionalities from corresponding modules
2import { sort } from 'algorithm';
3import { vector, pair, make_pair } from 'vector';
4import { string } from 'string';
5
6// Define a function to find and return the relative ranks of athletes based on their scores.
7function findRelativeRanks(scores: number[]): string[] {
8    const numOfScores: number = scores.length;
9
10    // Create an array to keep track of the scores along with their original indices.
11    const indexedScores: Array<pair<number, number>> = [];
12    for (let i = 0; i < numOfScores; ++i) {
13        indexedScores.push(make_pair(scores[i], i));
14    }
15
16    // Use a custom comparator function for sorting the indexed scores in descending order.
17    indexedScores.sort((a: pair<number, number>, b: pair<number, number>): number => b.first - a.first);
18
19    // Prepare an array to hold the rank strings, initially empty.
20    const ranks: string[] = new Array<string>(numOfScores);
21
22    // Define medal strings for the top 3 ranks.
23    const medals: string[] = ["Gold Medal", "Silver Medal", "Bronze Medal"];
24
25    // Loop through the sorted scores to assign ranks or medals.
26    for (let i = 0; i < numOfScores; ++i) {
27        if (i < 3) {
28            // Assign medals to the top 3 athletes.
29            ranks[indexedScores[i].second] = medals[i];
30        } else {
31            // For the other athletes, assign their rank as a string (1-indexed).
32            ranks[indexedScores[i].second] = (i + 1).toString();
33        }
34    }
35
36    return ranks;
37}
38
39// The TypeScript syntax requires type annotations for parameters and variables.
40// The standard JavaScript Array and sort functions are used in place of std::vector and std::sort.
41// Note: TypeScript does not have an equivalent of std::pair, but you can use tuples or define an interface.
42
43// Note: The above code block is written with the assumption that the TypeScript environment would mimic C++ functionality and modules, which is not the case in a standard TypeScript/JavaScript setup.
44// In a standard TypeScript environment, the `algorithm` or `vector` modules do not exist, and JavaScript's array methods would be used for tasks such as sorting.
45

Not Sure What to Study? Take the 2-min Quiz：

Which of the following problems can be solved with backtracking (select multiple)

Generating subsetsGenerating random numbersGenerating permutationsSorting integers

Time and Space Complexity

The time complexity of the provided findRelativeRanks function is O(n log n) where n is the number of athletes (the length of the input score list). This is because the function is performing a sort operation on a list of n indices, which is the most time-consuming part of the algorithm. The sorting function itself has a time complexity of O(n log n).

After sorting, the function traverses the sorted indices once, creating a result list of ranks. This traversal is linear with respect to the number of athletes, giving it a time complexity of O(n). However, this linear traversal does not dominate the sorting complexity, so the overall time complexity remains O(n log n).

The space complexity of the algorithm is O(n). We have idx and ans lists, each of size n. The top3 list is of constant size and does not scale with n, so it does not affect the asymptotic space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

506. Relative Ranks

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings