Binary Search implementation: HackerRank - Climbing the Leaderboard

Question

My code passes 11 out of 12 test cases. I was wondering where I can improve my code. NOTE: This code needs performance improvement, as it is working for most of the cases. To mu knowledge it would work for all the test cases where the size of arrays is smaller than 200.

Here is the question:

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.
For example, the four players on the leaderboard have high scores of 100, 90, 90, and 80. Those players will have ranks 1, 2, 2, and 3, respectively. If Alice's scores are 70, 80 and 105, her rankings after each game are 4, 3 and 1.

And here is my code:

#!/bin/python3
import math
import os
import random
import re
import sys
# Complete the climbingLeaderboard function below.
def binSearchMod(list1, value, start, end): #implemented for descending order
 mid = (start+end)//2
 #print('Looking for value: ', value, ' in ', start, end, mid , 'list :', list1)
 #conditions for element at start or end or mid
 if value==list1[start]:
 mid = start
 if value == list1[end]:
 mid = end
 if value == list1[mid]:
 return [True, mid] 
 if end-start == 1: # if some element lies in between 2 numbers of array
 #print('Found between ', start, end)
 return [False, start]
 if value < list1[mid]:
 return binSearchMod(list1, value, mid, end)
 else:
 return binSearchMod(list1, value, start, mid)
def climbingLeaderboard(scores, alice): # O(log n), not really we have to go through all scores to determine their rank
 res=[]
 rank =1
 rankScores=[scores[0]] 
 #ssign ranks to scores
 for score in range(1,len(scores)):
 if scores[score]!=scores[score-1]:
 rank+=1
 rankScores.append(scores[score])
 
 for ascore in alice:
 if ascore<scores[len(scores)-1]: # alice scores are smaller than all
 res.append(len(set(scores))+1)
 elif ascore > scores[0]: #alice score is greatest
 res.append(1)
 else: #alice score lies somewhere in between
 bsResult = binSearchMod(rankScores, ascore, 0 , len(rankScores)-1)
 #print(ascore, bsResult)
 if bsResult[0]:
 res.append(bsResult[1]+1)
 else:
 res.append(bsResult[1]+2)
 return res

I am guessing I'm trying to improve on test cases with length of arrays containing all scores and alice scores are > 200.

• greybeard: Welcome (again) to CodeReview@SE. You should probably move your assessment of correctness and execution time to the top of your post - if the result is incorrect, it is not ready for review here.
• Alex Povel: @greybeard, again, I do not understand how this question is off-topic. It seems on-topic for the same reasons as here.
• greybeard: (@AlexPovel I suggested moving an assessment to an eye-catching place - to support assessments of suitability of this question for CodeReview@SE, too. FWIW, it hasn't been me voting to close.)

Answer 1

You are on the right track. However, implementing your own bisection algorithm is not a good idea. Python has the built-in ("batteries included") bisect module, containing all the bisection algorithms we need. They are implemented in Python, but overridden by fast C implementations if those are available, which would then be as fast as we can hope for.

The from bisect import bisect (with the bisect function as an alias for bisect_right) replaces your binSearchMod function. In the code at the bottom, there is a "manual" bisect implementation without recursion, which is also a step forward. It is probably best to avoid recursion if (much) simpler means are available.

In your base climbingLeaderboard function, you have

 if ascore<scores[len(scores)-1]: # alice scores are smaller than all
 res.append(len(set(scores))+1)
 elif ascore > scores[0]: #alice score is greatest
 res.append(1)

which handles special cases. These cases are not special enough to warrant this, and are code smell. Your basic search algorithm should return correct results to append to res on its own, as we will see shortly. See also import this: Special cases aren't special enough to break the rules..

As an aside, slicing (using slice objects) makes indexing sequences much easier: scores[len(scores)-1] is just scores[-1]. Further, you return a list using

return [False, start]

This is a bad idea. You later use it to index into it, but that job can better be done by a tuple. Simply calling

return False, start

will return a tuple. This can be unpacked into two variables in one assignment, or indexed into just like lists. Tuple unpacking is convenient and easy to read.

The distinction between lists and tuples is important: lists are (should be) homogeneous, aka contain a sequence of elements of the same type (think filenames). Tuples are heterogeneous, aka the position of elements has meaning and they are of different types. In your example here, this would be bool and int, which have different semantics.

---

A key aspect to realize is that duplicate scores in the leaderboard can just be tossed, since they do not count towards anything. This calls for a set implementation. This also automatically gets rids of your

 #ssign ranks to scores
 for score in range(1,len(scores)):
 if scores[score]!=scores[score-1]:
 rank+=1
 rankScores.append(scores[score])

code block, saving a whole \$ \mathcal{O} (n) \$ iteration.

Since bisect relies on ascending order, while the input is sorted in descending order, a call to sorted is required, which automatically returns a list.

bisect(sequence, item) will return the index where to insert item in sequence while retaining order. If items compare equal, item is inserted to the right of existing items. If a list of scores in ascending order is [20, 30, 50], then Alice is really in second place if she scored 30. bisect_left would sort her into third place.

Since ranks are 1-indexed, increment by 1. Lastly, the below result would be inverted, since the sorting inverted the list. Therefore, use len to rectify.

#!/bin/python3
import math
import os
import random
import re
import sys
from bisect import bisect
# Complete the climbingLeaderboard function below.
def climbingLeaderboard(scores, alice):
 length = len(scores)
 return [length - bisect(scores, alice_score) + 1 for alice_score in alice]
if __name__ == '__main__':
 fptr = open(os.environ['OUTPUT_PATH'], 'w')
 scores_count = int(input())
 scores = sorted(set(map(int, input().rstrip().split())))
 alice_count = int(input())
 alice = list(map(int, input().rstrip().split()))
 result = climbingLeaderboard(scores, alice)
 fptr.write('\n'.join(map(str, result)))
 fptr.write('\n')
 fptr.close()

This passes all tests. The required sorted step is \$ \mathcal{O}(n,円 \log n)\$, see here.

---

Without sorting the input, a bisect implementation that works on reversed sorted lists is required. The change compared to the original implementation (link above) is minimal, as seen below. if a[mid] < x: lo = mid+1 is simply inverted to if a[mid] > x: lo = mid+1 (I also formatted the code more).

Simply calling list((set(sequence)) on the scores will not work. Duplicates will be purged, but the order will be lost. Therefore, we simply construct a new list, using a set to block appending already seen elements, see here.

The below approach works, but similarly to yours, fails for long inputs in its naive version. This is why I added previous_higher_bound. This counter keeps track of what rank Alice was on in the past. It could also be named previously_lowest_rank or similar. This is passed to bisect to drastically tighten the searched range, allowing the tests to pass. Unfortunately, it also makes the approach more verbose.

# Complete the climbingLeaderboard function below.
def climbingLeaderboard(scores, alice):
 def reverse_bisect_left(sequence, x, lower_bound=0, higher_bound=None):
 """Return the index where to insert item x in list a, assuming a is sorted in reverse.
 """
 if lower_bound < 0:
 raise ValueError("lo must be non-negative")
 if higher_bound is None:
 higher_bound = len(sequence)
 while lower_bound < higher_bound:
 middle = (lower_bound + higher_bound) // 2
 if sequence[middle] > x:
 lower_bound = middle + 1
 else:
 higher_bound = middle
 return lower_bound, higher_bound
 def uniquelify_list(sequence):
 seen = set()
 return [int(x) for x in sequence if not (x in seen or seen.add(x))]
 def leaderboard_rank(scores, score, higher_bound=None):
 result, previous_higher_bound = reverse_bisect_left(scores, int(score), higher_bound=higher_bound)
 return result + 1, previous_higher_bound
 def get_ranks(scores, alice_scores):
 scores = uniquelify_list(scores)
 previous_higher_bound = len(scores)
 ranks = []
 for alice_score in alice_scores:
 result, previous_higher_bound = leaderboard_rank(scores, alice_score, previous_higher_bound)
 ranks.append(result)
 return ranks
 return get_ranks(scores, alice)