Relative Ranks - Video Solutions

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.