Leetcode – Relative Ranks Solution in Python

Spread the love

Introduction

Relative Ranks is an interesting problem presented on Leetcode that encompasses the concepts of sorting and mapping. It focuses on ranking elements in an array relative to each other. In this article, we will thoroughly analyze this problem and explore various approaches to solve it using Python.

The problem is described as follows:

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal”, and “Bronze Medal.

For example:

Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Approach 1: Sorting and Mapping

In this approach, we will start by sorting the scores while keeping track of their indices. Once sorted, we will map the top three scores to their respective medals and assign ranks to the rest.

Here is the Python code for this approach.

def findRelativeRanks(nums):
    # Sorting the scores along with their original indices
    sorted_indices = sorted(range(len(nums)), key=lambda i: nums[i], reverse=True)
    
    # Mapping indices to their relative ranks
    rank_map = {}
    for rank, index in enumerate(sorted_indices):
        if rank == 0:
            rank_map[index] = "Gold Medal"
        elif rank == 1:
            rank_map[index] = "Silver Medal"
        elif rank == 2:
            rank_map[index] = "Bronze Medal"
        else:
            rank_map[index] = str(rank + 1)
    
    # Building the result array
    return [rank_map[i] for i in range(len(nums))]

This approach has a time complexity of O(N log N) due to sorting, and a space complexity of O(N) due to the extra space used for mapping.

Approach 2: Using Numpy (Alternative Pythonic Way)

We can employ Numpy, a powerful library for numerical computing in Python, to make our solution more concise. Using Numpy, we can find the indices that would sort the array and directly use them for assigning ranks.

Here is how it’s done.

import numpy as np

def findRelativeRanks(nums):
    # Find the indices that would sort the array
    sorted_indices = np.argsort(nums)[::-1]
    
    # Array for the result
    result = [None] * len(nums)
    
    # Assign ranks
    medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
    for rank, index in enumerate(sorted_indices):
        if rank < 3:
            result[index] = medals[rank]
        else:
            result[index] = str(rank + 1)
    
    return result

This approach has the same time complexity as the first approach but is more concise due to the use of Numpy.

Approach 3: Using Sorting with Custom Key

Python’s sorting functions allow us to specify custom keys for sorting. We can utilize this feature to optimize our initial approach. We will sort a list of indices based on the scores they index into.

def findRelativeRanks(nums):
    # Sorting indices based on the scores
    sorted_indices = sorted(range(len(nums)), key=lambda i: -nums[i])
    
    # Assign ranks
    result = [None] * len(nums)
    medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
    for rank, index in enumerate(sorted_indices):
        if rank < 3:
            result[index] = medals[rank]
        else:
            result[index] = str(rank + 1)
    
    return result

This approach is similar to the first but uses the custom sorting key to make the code cleaner.

Testing the Solutions

To verify the correctness of these solutions, we can use some test cases.

scores = [10, 3, 8, 9, 4]
print(findRelativeRanks(scores))  # Output: ['Gold Medal', '5', 'Bronze Medal', 'Silver Medal', '4']

Conclusion

In this comprehensive article, we delved into the Relative Ranks problem on Leetcode and discussed multiple approaches to solving it using Python. We started with a basic sorting and mapping approach, explored a more Pythonic solution using Numpy, and saw how custom sorting keys can be employed for code cleanliness.

Leave a Reply