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:
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
Stateful Binary Search
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);
}
|