C++ :
vector<int> climbingLeaderboard(vector<int> scores, vector<int> alice) {
vector<int> position, alicePos;
int currentPos = 1, firstPos = 0, lastPos = 0, currentScore = 0, aliceCurrentPos = -1, prevPos = 0;
position.push_back(currentPos);
//get ranking pos
for(int i = 1; i < scores.size(); i++){
if(scores[i] < scores [i - 1]){
currentPos++;
}
position.push_back(currentPos);
}
//calculate alice pos
for(int j = 0; j < alice.size(); j++){
if(alice[j] < scores[scores.size() - 1]){
aliceCurrentPos = position[position.size() - 1] + 1;
}else if(alice[j] >= scores[0]){
aliceCurrentPos = 1;
}else{
if(j == 0){
currentPos = (firstPos + lastPos) / 2;
}else{
currentPos = prevPos;
}
aliceCurrentPos = -1;
firstPos = 0;
lastPos = scores.size() - 1;
currentScore = scores[currentPos];
while(aliceCurrentPos == -1){
if(alice[j] < currentScore && alice[j] >= scores[currentPos + 1]){
aliceCurrentPos = position[currentPos] + 1;
}else{
if(alice[j] < currentScore){
firstPos = currentPos + 1;
currentPos = (firstPos + lastPos)/2;
currentScore = scores[currentPos];
}else if (alice[j] > currentScore){
lastPos = currentPos - 1;
currentPos = (firstPos + lastPos)/2;
currentScore = scores[currentPos];
}else{
aliceCurrentPos = position[currentPos];
}
}
}
prevPos = currentPos;
}
alicePos.push_back(aliceCurrentPos);
}
return alicePos;
}Explanation:
Ok, this one had me debugging for some time due to the “Terminated due to timeout” status on Hackerrank. It was frustrating when all the smaller test cases passed but the 200,000 ones do not. Using a double for loop (O² time) does NOT work well here due to huge amount of data in several test cases.
In simple terms, this is a binary search in descending order. The first for loop (looping with i) gives a rank to all the scores in the scores vector. This is a dense ranking, so if 2 people have the same score, they are ranked at the same position.
The next for loop (looping with j) goes through each of Alice’s scores and rank them against the rest. We use a binary search here. When we get 1 of Alice’s score, the first thing we do is to check if the score is lower than the lowest score in scores vector or higher than the highest score in scores vector. If it is, assign them to the lowest rank from position vector or 1, then push to alicePos vector.
The next part is slightly more complicated. Check if the score we get is the 1st element from Alice’s score. If it is, assign the currentPos to check to be in the middle of the scores vector. If not, assign currentPos to prevPos, which is assigned later in the while loop. We then assign aliceCurrentPos (should be aliceCurrentRank actually) to -1, firstPos to 0 (start of scores vector), lastPos to scores.size – 1 (end of scores vector) and currentScore to scores[currentPos].
The while loop will loop until aliceCurrentPos is no longer -1. This ensures that Alice’s score will be some positive number. The outer if checks if Alice’s score at index j is smaller than the score at index currentPos of score vector, and greater than or equals to ( >= ) the score at index (currentPos + 1) of score vector. If yes, we have found a suitable rank for Alice’s score at index j, which is the rank at position[currentPos] + 1.
Otherwise, we go into the nested for loop. If Alice’s score at index j is smaller than the currentScore, we set the firstPos to currentPos + 1. This indicates that we will search in the 2nd half of the scores vector. If Alice’s score at index j is larger than the currentScore, we set the lastPos to currentPos – 1, and this indicates that we will search in the 1st half of the scores vector. Otherwise, we have found the same score for Alice as the currentScore, and can simply get the rank from position vector and push it to alicePos vector.
Once we have found Alice’s rank, we keep currentPos in prevPos variable to avoid having search through the entire scores array. Instead, we can start from the prevPos (previous currentPos). This step is important to prevent the annoying “Terminated due to timeout” status.
Final note: Do NOT leave print statements in the loops, the printing itself may actually cause the “Terminated due to timeout” errors. Learnt that the hard way :[
