Skip to main content
Talentd

Relative Ranks - Solution & Explanation

EasyArraySortingHeap (Priority Queue)18 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

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.

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.

The solution involves creating a pair structure (ScoreIndex) to hold both the score and its original index. We make use of qsort to sort the array in descending order based on scores. After sorting, the rank is assigned according to the sorted position, converting the top three into medal strings and others into strings of their positions. Finally, the ranks are filled into the result array based on original indices.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), where n is the number of scores, for the sorting operation.
Space Complexity: O(n) for storing the pair struct array and the result array.

Try this approach in the editor →

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.

This C solution sorts a copy of the original list and uses the sorted positions to determine ranks. The qsort function provides a sorted view, and scores are ranked by finding their positions in this sorted list. Medals are assigned for the top three ranks using conditional checks.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) from sorting.
Space Complexity: O(n) due to storage of the sorted copy.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting with Index Mapping

Time Complexity: O(n log n), where n is the number of scores, for the sorting operation.
Space Complexity: O(n) for storing the pair struct array and the result array.

HashMap to Determine Ranks

Time Complexity: O(n log n) from sorting.
Space Complexity: O(n) due to storage of the sorted copy.

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting with Index MappingO(n log n)O(n)General solution when you need to rank values but keep original indices
HashMap to Determine RanksO(n log n)O(n)Useful when separating rank computation from final result lookup

Video Solution

Relative Ranks | 3 Approaches | Leetcode 506 | codestorywithMIK • codestorywithMIK • 5,980 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Relative Ranks with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays