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)
