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: enter image description here

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?

• 200_success: Welcome to Code Review! Please explain / summarize what the challenge task is, so that the question makes sense even if the link goes dead.
• MM360: Hi, @200_success I have inserted a screenshot of the original problem.
• MM360: I have solved this optimisation, thread can be closed. Thanks
• 200_success: We don't delete questions on Code Review just because you have solved the challenge yourself. Rather, you should post an answer to your own question that explains your successful approach and your thought process, so that future readers can benefit from this post.
• MM360: I have posted a comment under Anab's proposals with a brief summary of how I solved it in the end.

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?

• MM360: Thanks @Anab I removed the linear search per iteration and made use of the fact that my binary search returns the index if it finds the value in the list. Passed all cases
• Anab: Glad that it worked for you. Could you accept the answer if you're satisfied with it?