Climbing the Leaderboard

See the original problem on HackerRank.

Solutions

This problem has two main solutions. The first fully exploits the structure of the constraints, the second is more general.

Tradeoffs of both:

  • we remove all the duplicates. In a different context this could be forbidden and then we would have to use extra space or another logic;
  • we don’t really change the score table. Instead, in a real game it’s very likely that we need to update the current scores (e.g. for visualization).

Stateful Linear

For each Alice’s score \(score\), we iterate through current scores backwards from \(curr=n-1\).

If \(score\) is larger than the leaderboard’s \(curr\), we’ll decrement \(curr\), iterating through the scores in the leaderboard and stop when we find a score that \(score\) is not greater than.

We have 3 cases:

  • \(curr = -1\): \(score\) is bigger than every other score. Alice’s rank is 1,
  • \(scores[curr] = score\): Alice’s rank is the same as \(curr + 1\) (1-based),
  • \(scores[curr] > score\): Alice’s rank is one more than \(curr + 1\) (1-based).

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    
    int n, m, score;
    cin >> n;
    vector<int> scores(n);
    copy_n(istream_iterator<int>(cin), n, begin(scores));
    scores.erase(unique(begin(scores), end(scores)), end(scores));
    cin >> m;
    int curr = scores.size()-1;
    while (m--)
    {
    	cin >> score;
    	auto rank = 0;
    	
    	while (curr >= 0 && score >= scores[curr]) 
    		curr--;
    	
    	if (curr == -1) 
    		rank = 1;
    	else if (score == scores[curr]) 
    		rank = curr+1;
    	else if (score < scores[curr]) 
    		rank = curr+2;
    	
    	cout << rank << "\n";
    }
    

Pros:

  • linear

Cons:

  • maintains a state among the iterations

Stateless Binary Search

\(scores\) is sorted in descending order, so we could use the binary search to quickly lookup the array.

For each Alice’s score \(s\) we need to find the first score that is greater or equal than \(s\). The 1-based position of such score results in Alice’s rank:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int n, m, score;
cin >> n;
vector<int> scores(n);
copy_n(istream_iterator<int>(cin), n, begin(scores));
scores.erase(unique(begin(scores), end(scores)), end(scores));
cin >> m;   
while (m--)
{
	cin >> score;
	auto lb = lower_bound(begin(scores), end(scores), score, greater<>{});
	cout << (distance(begin(scores), lb)+1) << "\n";       
}

Pros:

  • stateless: each iteration is independent from the others (we can use this method for querying the table randomly)
  • simple

Cons:

  • slower than the other solution

In this variant, for each step we use the position \(ub\) found at the previous to narrow the binary search into \(begin-ub\). Compared to the previous solution this is clearly faster:

1
2
3
4
5
6
7
8
auto ub=end(scores);
while (m--)
{
	cin >> score;
	auto lb = lower_bound(begin(scores), ub, score, greater<>{});
	cout << (distance(begin(scores), lb)+1) << "\n";
	ub = lb;
}

Pros:

  • quicker than the previous solution
  • simple

Cons:

  • still a bit slower than the first one
  • maintains a state among the iterations

Another solution that doesn’t allocate space for returned array, but overwrites the input array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void climbingLeaderboard(int scores_count, int* scores, int alice_count, int* alice)
{
    int minScore = -1;
    int i, j, rank;
    int* unique_scores;
    int unique_scores_count = 0;

    unique_scores = malloc(sizeof(int) * scores_count);

    /* Create an array of unique scores, in ascending order */
    for (i = scores_count - 1; i >= 0; i--)
    {
        if (scores[i] > minScore)
        {
            minScore = scores[i];
            unique_scores[unique_scores_count] = minScore;
            unique_scores_count = unique_scores_count + 1;
        }
    }

    rank = unique_scores_count + 1;
    for (j = 0; j < alice_count; j++)
    {
        /* Don't start from zero each time */
        for (i = unique_scores_count - rank; i < unique_scores_count; i++)
        {
            if (alice[j] >= unique_scores[i])
            {
                rank = unique_scores_count - i;
            }
            else
            {
                /* If the current player score is bigger than Alice's,
                   we're sure all the other following scores will be bigger,
                   so we can break now.
                 */
                break;
            }
        }
        alice[j] = rank;
    }

    free(unique_scores);
}
We've worked on this challenge in these gyms: modena  milan  padua  turin 
comments powered by Disqus