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
time complexity is O(N*log(N))
space complexity is O(1)
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.