Leaderboards are a great way for people to gauge and improve their skills. Sports teams, universities, and competitive programming all use leaderboards. Leaderboards display the rank of each player in comparison with other players.
Create a function that will show the player’s ranking on the leaderboard after each round using dense ranking. Dense ranking gives players with the same score the same rank. The next player is assigned the ranking number immediately following. Players with scores of 100, 100, 95, 90, 90 have the ranking of 1, 1, 2, 3, 3.
This problem is an algorithm interview preparation question on HackerRank. The input is a list of ranks in descending order and a list of scores in ascending order.
Input:
ranked = [100, 90, 80, 80, 80, 70, 70, 35, 10]
player = [0, 5, 75, 85, 100]
Output:
[7, 7, 4, 3, 1]
Input:
ranked = [365, 365, 365, 270, 180, 90]
player = [75, 100, 270, 360]
Output:
[5, 4, 2, 2]
Input:
ranked = [100, 90, 80]
player = [80, 90, 100]
Output:
[3, 2, 1]
There are several logical approaches to solving this problem. The method below will keep the ranks and player scores in the original order without re-sorting the input data.
The brute force or native approach uses a for loop to remove the duplicates. It uses two additional data structures and one additional function. The function finds the midpoint of the list to find the index of the player rank. The overall time complexity is O(n2).
Step 1: Start.
Step 2: Create two lists.
Step 3: Loop through the ranked list to remove the duplicates.
Step 3.1 If the rank is not in the ranked_scores list, add it.
Step 4: Loop through the player list to find the rank.
Step 4.1 If the score is in ranked_scores, get the index.
Step 4.1.a Add the index + 1 to the player_ranking list.
Step 4.2 If the score is not in ranked_scores, call ranked_index to find the rank index.
Step 4.4 Add the index + 1 to the player_ranking list.
Step 5: Return the player_ranking list.
Step 1: Start.
Step 2: Set start_index to 0.
Step 3: Set the stop_index to the length of the input list.
Step 4: Calculate the midpoint.
Step 5: Search for the rank:
Step 5.1 If the midpoint score is > score:
Step 5.1.a: Set start_index to midpoint.
Step 6: Loop from start_index to stop_index.
Step 6.1.a: If score is > the score_list[score_index], return store_index.
Step 7: Return score_index + 1.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def climbing_leaderboard(ranked, player):
ranked_scores = []
player_ranking = []
for rank in ranked:
if rank not in ranked_scores:
ranked_scores.append(rank)
for score in player:
if score in ranked_scores:
player_index = ranked_scores.index(score)
player_ranking.append(player_index + 1)
else:
player_index = rank_index(ranked_scores, score)
player_ranking.append(player_index + 1)
return player_ranking
def rank_index(score_list, score):
start_index = 0
stop_index = len(score_list)
midpoint = len(score_list) // 2
if score_list[midpoint] > score:
start_index = midpoint
for score_index in range(start_index, stop_index):
if score > score_list[score_index]:
return score_index
return score_index + 1
The efficient approach uses a dictionary subclass and a modified binary search algorithm. Python OrderedDict creates a dictionary and removes the duplicate ranks while preserving the order. OrderedDict has a time complexity of O(1). The modified binary search algorithm has a time complexity of O(log n). The overall time complexity of this approach is O(n log n).
Step 1: Start.
Step 2: Create one list.
Step 3: Remove the duplicate ranks using OrderedDict and assign the results to ranked_no_dup.
Step 4: Loop through the player list to find the rank.
Step 4.1 Call the find_rank function.
Step 4.2 Append the results of find_rank to the player_rankings list.
Step 5: Return player_rankings list
Step 1: Start.
Step 2: Set low to 0.
Step 3: Set high to the length of rankings -1.
Step 4: Define the edge cases. The edge cases give the best-case time complexity of O(1).
Step 4.1: Return the low + 1 value if rankings[low] is <= the score.
Step 4.2: Return high + 1 if the value of ranking[high] is = to the score.
Step 4.3: Return the high +2 if ranking[high] is greater than score:
Step 5: While low <= high
Step 5.1 Set mid to (low + high) // 2
Step 5.2 If rankings[mid] = to score, return mid + 1
Step 5.3 If rankings[mid] < score, set high = mid =1
Step 5:4 Else set low = mid + 1
Step 6: Return low + 1
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from collections
import OrderedDict
def climbing_leaderboard(ranked, player):
player_rankings = []
ranked_no_dup = list(OrderedDict.fromkeys(ranked))
for score in player:
player_rankings.append(find_rank(score, ranked_no_dup))
return player_rankings
def find_rank(score, rankings, mid = None):
high = len(rankings) - 1
low = 0
# Edge Cases--Although the search will handle the edge cases,
# defining an edge
case will result in a time
# complexity of O(1) instead of O(log n)
.
if rankings[low] <= score:
return low + 1
if rankings[high] == score:
return high + 1
if rankings[high] > score:
return high + 2
# Find ranking - uses a modified binary search algorithm.
# Time complexity is O(log n)
.
while low <= high:
mid = (low + high) // 2
if rankings[mid] == score:
return mid + 1
elif rankings[mid] < score:
high = mid - 1
else:
low = mid + 1
return low + 1