python – Climbing the leaderboard (Hacker Rank) via binary search

I see three ways to improve your runtime. I have never done this problem so I can’t guarantee that it will be enough to pass all the tests.

Sorted input

The leaderboard scores are sorted in decreasing order. Your duplicate-removal code converts a sorted list to a set to remove duplicates (O(n)), then converts it back to a list (O(n)), then sorts it (O(n*log(n)). You could use the fact that it is sorted: duplicates will always be side by side. You could do something like the following, for example:

prev = ranked(0)
duplicateIndices = set()
for index, val in enumerate(ranked(1:), 1):
    if val == prev:
        duplicateIndices.add(index)
    prev = val
ranked2 = (x for i,x in enumerate(ranked) if i not in duplicateIndices)

This may not be the most efficient way to remove duplicate but it runs in O(n).

Sorted input 2

player is sorted as well. That means that after each iteration, the player’s rank is at most the previous one. This has two consequences:

  1. You don’t need to add the player’s score to ranked2 (either two consecutive scores are equal, which is easy enough to detect without altering ranked2, or the second one is strictly better than the first and having inserted the first in ranked2 will not change the insertion point of the second)
  2. The right boundary of your binary search is your previous insertion point.

This will not change your asymptotical complexity but it should have an interesting effect on your runtime anyway.

Skipping the linear search

With a single line, your code goes from O(m*log(n)) to O(m*n). Since ranked2 is a list, and Python does not know that it is sorted, if i in ranked2 will iterate over the entire list searching for a match. This operation runs in O(n) and is repeated for each of the player’s score. Besides, you have already handled the equality case in your binary search, so why bother?