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.

• 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 scores(n); copy_n(istream_iterator(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 scores(n); copy_n(istream_iterator(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