1
\$\begingroup\$

Climbing the Leaderboard

An arcade game player wants to climb to the top of the leaderboard and track their 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.

Example

\$ranked = [100, 90, 90, 80]\$

\$player = [70, 80, 105]\$

The ranked players will have ranks 1, 2, 2, and 3, respectively. If the player's scores are 70, 80 and 105, their rankings after each game are 4th, 3rd and 1st. Return [4, 3, 1].

Function Description

Complete the climbingLeaderboard function in the editor below.

climbingLeaderboard has the following parameter(s):

  • int ranked[n]: the leaderboard scores
  • int player[m]: the player's scores

Returns

  • int[m]: the player's rank after each new score

Input Format

The first line contains an integer \$n\$, the number of players on the leaderboard. The next line contains space-separated integers \$ranked[i]\$, the leaderboard scores in decreasing order. The next line contains an integer, \$m\$, the number games the player plays. The last line contains space-separated integers \$player[i]\$, the game scores.

Constraints

  • \$1 <= n <= 2 x 10^5\$
  • \$1 <= m <= 2 x 10^5\$
  • \$0 <= ranked[i] <= 10^9\$ for \$0 <= i < n\$
  • The existing leaderboard, \$ranked\$, is in descending order.
  • The player's scores, \$scores\$, are in ascending order.

Subtask

For \$60%\$ of the maximum score:

  • \$1 <= n <= 200\$
  • \$1 <= m <= 200\$

Sample Input 1

7 
100 100 50 40 40 20 10 
4 
5 25 50 120 

Sample Output 1

6 4 2 1

I keep getting timed out. I think my general logic is right but how can my code be optimized more?

I know there are solutions using the bisect module but I've seen very simple ones without using that. From what I can think of, maybe using while loops will speed things up?

def climbingLeaderboard(ranked, player):
    ranked=[i for n, i in enumerate(ranked) if i not in ranked[:n]] #remove duplicates
    
    player_rank=[]

    ranking=len(ranked)+1
    start=1
    for pi,ps in enumerate(player[::-1]):
        for ri,r in enumerate(ranked,start=start):
            if ps>=r:
                player_rank.append(ri)
                break
            else:
                ranked=ranked[1:]
                start+=1
        else:
            player_rank.append(ranking)
           
    return player_rank[::-1]
New contributor
Mysterious Shadow is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
1
  • \$\begingroup\$ Are you sure the code works at all? \$\endgroup\$
    – vnp
    Nov 25 at 0:22
2
\$\begingroup\$

Removing duplicates efficiently

ranked=[i for n, i in enumerate(ranked) if i not in ranked[:n]]

This line creates a copy of ranked at each iteration, which makes it inefficient. Since ranked is already sorted, create a new list and add elements one by one if different from the previous.

Alternatively, you can use a dictionary that is ordered from Python 3.7.

ranked = list(dict.fromkeys(ranked))

Rank assignment

The second part of the algorithm creates many copies of ranked in ranked=ranked[1:], which might be the issue. As you said, using a while loop can speed things up. Refactored code:

def climbingLeaderboard(ranked, player):
    ranked = list(dict.fromkeys(ranked))
    player_rank = []
    ranking = len(ranked) + 1
    start = 0
    for pi, ps in enumerate(player[::-1]):
        j = start
        while j < len(ranked):
            if ps >= ranked[j]:
                player_rank.append(j + 1)
                break
            start += 1
            j += 1
        if j == len(ranked):
            player_rank.append(ranking)
    return player_rank[::-1]
\$\endgroup\$
2
  • \$\begingroup\$ Thanks it worked! I think ranked=ranked[1:] was the problem. I'm a bit new to code optimization, can you explain more about how that creates many copies of ranked? \$\endgroup\$ Nov 25 at 22:47
  • \$\begingroup\$ @MysteriousShadow I am glad I could help. ranked=ranked[1:] creates many copies because it's in the for-loop. \$\endgroup\$
    – Marc
    Nov 26 at 1:39

Your Answer

Mysterious Shadow is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.