Teaching Kids Programming – Leaderboard Algorithm: Compute the Ranking of Numbers

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of integers nums, representing the number of chess matches each person has won. Return a relative ranking (0-indexed) of each person. If two players have won the same amount, their ranking should be the same.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [50, 30, 50, 90, 10]
Output
[1, 2, 1, 0, 3]

Compute the Ranking of Numbers

First, we need to remove the duplicates. This can be done via a set.

Second, we need to sort the numbers from largest to smallest, and then construct a mapping from value to the index (which is also the ranking).

Lastly, we need to go through the original numbers and then look up their rankings in the table.

class Solution:
    def rankingTable(self, nums):
        # remove duplicates
        data = list(set(nums))

        # sort from largest to smallest
        data.sort(reverse=True)

        rank = {}
        for b, a in enumerate(data):
            rank[a] = b
        
        ans = []
        for n in nums:
            ans.append(rank[n])
        return ans

We can simplify the implementations of the second and the third step by one-liners:

class Solution:
    def solve(self, nums):
        # remove duplicates
        data = list(set(nums))

        # sort from largest to smallest
        data.sort(reverse=True)

        rank = {a: b for b, a in enumerate(data)}

        return [rank[n] for n in nums]

The time complexity is O(NLogN) because of sorting. And the space complexity is O(N) due to the additional array and the mapping table.

–EOF (The Ultimate Computing & Technology Blog) —