How to optimize o(n**2) algorithm to become o(nlogn) or o(n)?

Question

I am trying to complete a hackerrank problem where you are given two arrays. One being a list of scores and another being a list of scores from a specific person. You have to determine the ranking of that person for each score. For example:

scores = [100,90,80]
alice = [80,90,100]

The output should be 3,2,1 because that is how alice would place if you were to compare it with the scores in the array scores. If you tie, then you take the same ranking.

I have tried using only one loop and using the range command but that completely failed and I am not getting remotely close answers. The working solution is a o(n**2) solution and it passes all the tests except the big ones, in which it times out.

def climbingLeaderboard(scores, alice):
    scores = list(set(scores))
    new_list = []
    alcount = 1
    for i in alice:
        for x in scores:
            if i < x:
                alcount += 1
        new_list.append(alcount)
        alcount = 1
    return new_list

Any help would be greatly appreciated!

Answer 1

Put the scores into a dict:

scores = {100:1, 90:2, 80:3}

Now it's a direct look-up for each of Alice's scores to convert to the desired output list.