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
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 Onotation to O(N).
3) Take advantage of builtin 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() 