Climbing the leaderboard (Hacker Rank) via binary search

Question

I am trying to solve the Climbing the leaderboard problem on Hacker Rank. My code passes all the test cases except Test Cases 6 to 9, which I assume are using large data sets.

I'm using binary search to find the optimal insertion point for each score and using the index as the rank. I know there are loads of solutions online but I want to pass the test cases with my own code.

Original problem:

def climbingLeaderboard(ranked, player):
    
    climb = []

    ranked2 = sorted(set(ranked),reverse = True)
    
    for i in player:
        if i in ranked2:
            climb.append(ranked2.index(i)+1)
        elif i > ranked2[0]:
            climb.append(1)
            ranked2.insert(0, i)
        elif  i < ranked2[-1]:
            climb.append(len(ranked2) + 1)
            ranked2.append(i)
        else:
            a = binary_search(ranked2, i, 0,len(ranked2))
            climb.append(a+1)
            ranked2.insert(a, i)
        
    return climb


def binary_search(arr, n, lo, hi):
    
    mid = int((hi+lo)/2)
    
    if lo > hi:
        return lo
    elif arr[mid] < n:
        return binary_search(arr, n, lo, mid -1)
    elif arr[mid] > n:
        return binary_search(arr, n, mid + 1, hi)
    else:
        return mid

Where can I optimise my code?

Answer 1

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?