HackerRank ‘Climbing The Leatherboard’ Solution

H
Short Problem Definition:

Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. The game uses Dense Ranking, so its leaderboard works like this:

  • The player with the highest score is ranked number 1 on the leaderboard.
  • Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number
Link

Climbing The Leaderboard

Complexity:

time complexity is O(N*log(N))

space complexity is O(1)

Execution:

I am not a fan of the Dense Rank. Standard Competition ranking makes much more sense.

1) In the Dense Rank, duplicates have no impact on the ranking, so they can be safely removed.

2) The array should be sorted. Since the value range is fairly small (10^5), counting sort would improve the theoretical O-notation to O(N).

3) Take advantage of built-in Python functionality. Bisect right finds an insertion point after potential duplicates, giving us the correct Dense Rank.

Solution:
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
#!/bin/python
 
import math
import os
import random
import re
import sys
import bisect
 
# Complete the climbingLeaderboard function below.
def climbingLeaderboard(scores, alice):
    res = []
    s = sorted(list(set(scores)))
    l = len(s)
    for v in alice:
         res.append(l - bisect.bisect_right(s, v) +1)
             
    return res
 
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    scores_count = int(raw_input())
    scores = map(int, raw_input().rstrip().split())
    alice_count = int(raw_input())
    alice = map(int, raw_input().rstrip().split())
    result = climbingLeaderboard(scores, alice)
    fptr.write('n'.join(map(str, result)))
    fptr.write('n')
    fptr.close()

About the author

Add comment

Archives

Categories