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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

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:

1
2
3
4
5
6
7
8
9
10
11

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]

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) —