HackerRank leaderboard challenge

Question

I have been doing this challenge in which I need to determine and return one's (i.e. alice) rank on a leaderboard by comparing her scores to the others'. I made this work in all but this one case where there are 200000 scores on the board, so I believe my program is not effective at large scale. I am receiving a timeout error. I tried to shorten the program as much as possible but I think loops are still too much of a problem. I would appreciate any suggestions.

#include <bits/stdc++.h>
using namespace std;
vector <int> climbingLeaderboard(vector <int> scores, vector <int> alice) {
 vector<int> result;
 reverse(alice.begin(), alice.end());
 int lastIndex = 0;
 int lastRank = 1;
 for (int i = 0; i < alice.size(); i++) {
 int rank = lastRank;
 for (int j = lastIndex; j < scores.size(); j++) {
 if (alice[i] >= scores[j]) {
 lastIndex = j;
 break;
 }
 else if (alice[i] < scores[j]) {
 rank++;
 }
 if (scores[j] == scores[j+1] && rank != 1) {
 rank--;
 }
 }
 result.push_back(rank); 
 lastRank = rank;
 }
 reverse(result.begin(), result.end());
 return result;
}
int main() {
 int n;
 cin >> n;
 vector<int> scores(n);
 for(int scores_i = 0; scores_i < n; scores_i++){
 cin >> scores[scores_i];
 }
 int m;
 cin >> m;
 vector<int> alice(m);
 for(int alice_i = 0; alice_i < m; alice_i++){
 cin >> alice[alice_i];
 }
 vector <int> result = climbingLeaderboard(scores, alice);
 for (ssize_t i = 0; i < result.size(); i++) {
 cout << result[i] << (i != result.size() - 1 ? "\n" : "");
 }
 cout << endl;
 return 0;
}

Sample Input

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

Sample Output

6
4
2
1

Explanation

The second row of input is composed of the scores on the leaderboard and the fourth row contains the scores of Alice. The score she gets during each attempt is compared with other scores on the leaderboard to determine her rank. Dense Ranking is used here. So from the sample input, the first two 100s on the leaderboard rank 1st and then 50 ranks the 2nd, both 40s rank 3rd and so on.

Answer 1

don't use using namespace std

You should not use using namespace std because it eliminates some important information, which may lead to some conflicts with your classes or classes of other libraries. It is not uncommon to have a vector class, which has a totally other meaning than the std::vector. And to be honest, it isn't that much more work, to type std:: in front of the classes/functions, is it?

use std algorithms

You do everything with for loops, which is bloated and error prone. Use the algorithms of the std namespace instead. I provide you with a short an clean example, how you could do the above task (and more) with less lines.

your algorithm itself

You should think about logical improvements. Is it necessary to store every score in a vector, when equal scores produce the same rankings, and the following scores just increments by one? Therefore I took the std::unique algorithm, which returns a forward iterator. std::unique doesn't erase anything itself. It just moves duplicates to the end of the range (our std::vector); you have to erase them manually. But, before you can use std::unique you have to order your elements. I don't know if it's guaranteed to get the score input in a descending order; thus I simply use std::sort to ensure this. After that, it's a simple std::lower_bound (which is a binary search instead a linear search) to get the first iterator to an element, which is not less than the provided score (ok, I had to pass an other function object, because we want to check for greater and not for less). Iterators starts with a zero index. This means, we have to add 1 to our index, to get the official ranking. Easy, huh?

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
int main()
{
 std::vector<int> scores { 100, 100, 50, 40, 40, 20, 10 };
 std::vector<int> aliceScores { 5, 25, 50, 120 };
 // sort and erase duplicates
 std::sort(std::begin(scores), std::end(scores), std::greater<int>());
 scores.erase(std::unique(std::begin(scores), std::end(scores)), std::end(scores));
 // just a lambda to make the output part more readable
 auto locateRanking = [](const auto& _scores, int _newScore){
 auto itr = std::lower_bound(std::begin(_scores), std::end(_scores), _newScore, std::greater<int>());
 return std::distance(std::begin(_scores), itr) + 1;
 };
 // output part
 for (auto newScore : aliceScores)
 {
 std::cout << locateRanking(scores, newScore) << std::endl;
 }
}

tl;dr

Sort the vector, remove the duplicates and use a binary search instead of your linear approach and you will discover a huge performance benefit.

• Jerry Coffin: You also gain a lot by using std::lower_bound, which does a binary search instead of a linear search.
• omnimiratus: This just showed how little I knew of this language, amazing! Actually I've tried to save some work by breaking the loop at a certain point during the search and by also starting the search from where previous loop left so that it wouldn't read the entire vector again, but it still wasn't enough. I'll try this tomorrow and get back with the result, thanks! (btw the input is always in descending order since it's a leaderboard)
• DNKpp: If you would know, that the scores of alice are also in a specific order, you could improve it. As you are already suggesting, you could store the index from the last search and start with the new one. But, this is a task, you can solve by your own ;)
• Blastfurnace: I just want to point out a common misunderstanding. std::unique doesn't move duplicates to the end of the range. The only data movement is non-duplicates toward the front of the range. The elements after the new logical end have unspecified values.
• DNKpp: Ok. std::lower_bound returns an iterator to the first element, which doesn't fits in the passed functor. In fact, we searched for a value, which is NOT std::greater than the passed value (alice score). That's it. That's the magic. std::distance just calculates the difference from the begin iterator to the iterator found by std::lower_bound. If it's the first value, the difference is 0. But we need the first element to be 1, thus we simply add 1 to the difference. Hopefully it's clearer now ;)

Answer 2

One strategy: Do binary split of scores, and for each split, keep track of the smallest number of alice that is greater than or equal to the largest element of each branch and the largest number of alice smaller than the smallest element of the branch. Once those two numbers are adjacent, don't split that branch any more. So, taking your example scores = 100 100 50 40 40 20 10 alice = 5 25 50 120. I'll split scores, with alice scores in brackets surrounding each branch in bold.

At iteration 0, I have

{[120]( 100 100 50 40 40 20 10 )[5]}

That is, I haven't done any splits, so everything is in the same branch. The largest number of the branch is 100, and the smallest number of alice larger than that is 120, so 120 goes on the left of the branch. The smallest number of the branch is 10, and the largest alice number smaller than that is 5, so 5 goes on the right.

In iteration 1, I have:

{[120](100 100 50 40)[25]} {[50](40 20 10)[5]}

iteration 2:

{[120](100 100)[50]}{[50](50 40)[25]} {[50](40 20 10)[5]}

Since there are no numbers in alice between 120 and 50, the first branch is done splitting. Since there are no numbers between 50 and 25, the second branch is also done. So the next iteration moves on to the third branch:

{[120](100 100)[50]}{[50](50 40)[25]} {[50](40 20)[5]} {[25](10)[5]}

Iteration 4:

{[120](100 100)[50]}{[50](50 40)[25]} ]} {[50](40)[25]}{[25](20)[5]} {[25](10)[5]}

At this point, I’ve done all the splits I can, and I can just read off the ranks; each rank of a number from alice is the count of distinct members from scores to the left of the first instance of it, plus one. 120 is all the way to the left, so its rank is 1. The first instance of 50 has one distinct element of scores to the left of it, so its score is 2. And so on.

The dense ranking requirement means that you'll have to get rid of duplicate members, but other than that this algorithm should be logarithmic time, rather than linear time for your algorithm.