[HackerRank] Climbing the Leaderboard

https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem

Solution

ref: https://inspirit941.tistory.com/199 Trying to solve it with Python list sort hit the time limit. Binary search didn’t help either.

1
def climbingLeaderboard(ranked, player):
2
    # Write your code here
3
    result = []
4
    from collections import defaultdict
5
    rank_dict = defaultdict(int)
6
    for r in ranked:
7
        rank_dict[r] += 1
8

9
    for p in player:
10
        score = list(rank_dict.keys())
11
        score.append(p)
12
        score.sort(reverse=True)
13
        for idx, s in enumerate(score):
14
            if s == p:
15
                break
16
        result.append(idx + 1)
17

18
    return result

To fix the time limit, you can’t search from scratch for every p. The key insight is that player is in ascending order and ranked is in descending order, so you can skip regions that don’t need searching.

1
def climbingLeaderboard(ranked, player):
2
    queue = sorted(set(ranked), reverse=True)
3

4
    idx = len(queue) - 1
5
    result = []
6

7
    for p in player:
8
        while queue[idx] <= p and idx >= 0:
9
            idx -= 1
10
        if idx < 0:
11
            result.append(1)
12
            continue
13
        result.append(idx + 2)
14
    return result

Because of the sort orders of player and ranked, earlier values in player correspond to later positions in ranked. So when iterating over player, we check ranked from the end. Once an index in the queue has been passed, there’s no need to revisit it. This way, no matter how large ranked is, we only traverse it once.

Negative Index

idx can become negative. This happens when all elements of ranked have been traversed. In that case, p is in 1st place, so we append 1 to the result.

Code

https://github.com/naem1023/codingTest/blob/master/implementation/hackerrank-climbing-the-leaderboard.py