Climbing the leaderboard: a simple yet elegant problem

                                           Introduction:

                                      Photo by Ethan Johnson on Unsplash

I have recently embarked upon the journey of getting a few stars in my cap by starting small-time coding in hackerrank. While I am only a 3-star noob there yet, I really liked one problem which I solved today. So in this post, we will discuss the solution and speed optimizations I had to implement to solve the problem.

The problem description:

The problem is climbing the leaderboard. The problem statement is simple. There is a leaderboard, where dense ranking method is used. i.e. if people get same marks, then they are assigned the same rank and then the next person to them in the list is assigned the next rank. For example, if there are 4 people in the rank board, and they have got marks respectively 100,90,90,80; then their ranks will be 1,2,2,3.

Now, the question is that one player comes into the competition and keeps solving problems and his/her rank keeps increasing. Then we have to find out, what is his/her rank after each step. 

The input in this is two arrays, one is a ranked array; the other one is a array player which contains all the scores the player gets. The output is basically you have to return the array of the ranks the player gets.

The solution:

This is the optimal solution. Behold my code :)

import math

import os

import random

import re

import sys

#

# Complete the 'climbingLeaderboard' function below.

#

# The function is expected to return an INTEGER_ARRAY.

# The function accepts following parameters:

#  1. INTEGER_ARRAY ranked

#  2. INTEGER_ARRAY player

#

def climbingLeaderboard(ranked, player):

    # Write your code here

    ranks = []

    vals = []

    for rank in ranked:

        if len(ranks) == 0:

            ranks.append(rank)

        elif rank ==ranks[-1]:

            pass

        else:

            ranks.append(rank)

    #print(ranks)

    rank_len = len(ranks)

    for play in player:

        if play<ranks[-1]:

            vals.append(rank_len+1)

            continue

        if play>=ranks[0]:

            vals.append(1)

            continue

        if play>=ranks[1]:

            vals.append(2)

            continue

        if len(vals) == 0:

           for i in range(rank_len-1,0,-1):

               if play<ranks[i]:

                   vals.append(i+2)

                   break

               if play == ranks[i]:

                   vals.append(i+1)

                   break

        else:

            for i in range(min(vals[-1]-1,rank_len-1),0,-1):

                if play<ranks[i]:

                    vals.append(i+2)

                    break

                if play == ranks[i]:

                    vals.append(i+1)

                    break

    return vals

if __name__ == '__main__':

    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    ranked_count = int(input().strip())

    ranked = list(map(int, input().rstrip().split()))

    player_count = int(input().strip())

    player = list(map(int, input().rstrip().split()))

    result = climbingLeaderboard(ranked, player)

    fptr.write('\n'.join(map(str, result)))

    fptr.write('\n')

    fptr.close()

Now, I will describe the heuristics and optimizations I have used in this code one by one.

First point which should come to your mind is that, this is basically a partial insertion sort kind of problem. i.e. given ranked and one instance of the player's score, you just have to check from the left to right of the ranks and check where the score fits; i.e. what is the index where ranked[i] is more than the score and ranked[i+1] is less than the score.

I followed this logic and created one implementation. Result was that I got timeout error in 4/12 cases. Why?

The reason is basically we end up missing two key points in such a solution. One is that if you surf from left to right, you keep running more; as the player is supposed to rise in ranking. So the first point to note is that, 

the checking starts from the last rank.

So the changed heuristic will be to basically check from the end; and log the number where first time ranked[i] is more than the score we are checking with. Now here is a common edge-case; which is that ranked[i] can be also equal to the score; and in such a case you get to assign a different rank to the score than the unequal case. This is why we have the following if blocks in the code.

if play<ranks[i]:
   vals.append(i+2)
   break

if play == ranks[i]:

   vals.append(i+1)

   break

The other important point is that, as we know that the score is increasing, so there is no meaning to start the search everytime from bottom. We should start the search from where we left last time. With a handling of few edge-cases, the code for that turns out in doing this. 

Now, still a few edge cases and a good optimization is left. One edge case is that if the score is more than all the scores in leaderboard, than in current format we will have to parse quite a few numbers in the leaderboard to get to the top of it. To stop this waste of computation steps, we add a check in the beginning. 

if play<ranks[-1]:
    vals.append(rank_len+1)
    continue
if play>=ranks[0]:
    vals.append(1)
    continue
if play>=ranks[1]:
    vals.append(2)
    continue

We extend this to checking for top 3 numbers and add this in the beginning.  Now, after putting all these changes, still I was getting 2 test cases timeout. Made me think, what is it that I am missing?

So as you might have guessed, we have repeated numbers in the ranked. So what I was doing was that I would initiate a list; and add ranks one by one by checking whether that number is even in the link. But this ends up creating lots of checks once we get into longer ranked list. So what is the easy thing to cut the number here? think for a minute if you want.

Yes, you got it right. As of dense ranking, even if the next number we are adding, can only be equal to the last number in the added unique rank's list. So I can just check if the new number is equal to the last number in the list and add if it is not. 

    for rank in ranked:

        if len(ranks) == 0:

            ranks.append(rank)

        elif rank ==ranks[-1]:

            pass

        else:

            ranks.append(rank)

This cleared the final 2 test cases and I achieved the score.

Thanks for reading! and I will come back tomorrow with more of these simple code posts!