c# - Hackerrank: Climbing the Leaderboard

Question

i have a deal with a hackerrank algorithm problem.

It works at all cases, except 6-7-8-9. It gives timeout error. I had spent so much time at this level. Someone saw where is problem?

static long[] climbingLeaderboard(long[] scores, long[] alice)  
{
    //long[] ranks = new long[scores.Length];
    long[] aliceRanks = new long[alice.Length]; // same length with alice length
    long lastPoint = 0;
    long lastRank;
    for (long i = 0; i < alice.Length; i++)
    {
        lastPoint = scores[0];
        lastRank = 1;
        bool isIn = false; // if never drop in if statement 
        for (long j = 0; j < scores.Length; j++)
        {
            if (lastPoint != scores[j])  //if score is not same, raise the variable
            {
                lastPoint = scores[j];
                lastRank++;
            }

            if (alice[i] >= scores[j])
            {
                aliceRanks[i] = lastRank;
                isIn = true;
                break;
            }
            aliceRanks[i] = !isIn & j + 1 == scores.Length ? ++lastRank : aliceRanks[i]; //drop in here
        }
    }
    return aliceRanks;
}

Answer 1

This problem can be solved in O(n) time, no binary search needed at all. First, we need to extract the most useful piece of data given in the problem statement, which is,

The existing leaderboard, scores, is in descending order.

Alice's scores, alice, are in ascending order.

An approach that makes this useful is to create two pointers, one at the start of alice array, let's call it "i", and the second is at the end of scores array, let's call it "j". We then loop until i reaches the end of alice array and at each iteration, we check for three main conditions. We increment i by one if alice[i] is less than scores[j] because the next element of alice may be also less than the current element of scores, or we decrement j if alice[i] is greater than scores[j] because we are sure that the next elements of alice are also greater than those elements discarded in scores. The last condition is that if alice[i] == scores[j], we only increment i.

I solved this question in C++, my goal here is to make you understand the algorithm, I think you can easily convert it to C# if you understand it. If there are any confusions, please tell me. Here is the code:

// Complete the climbingLeaderboard function below.
vector<int> climbingLeaderboard(vector<int> scores, vector<int> alice) {
    int j = 1, i = 1;
    // this is to remove duplicates from the scores vector
    for(i =1; i < scores.size(); i++){
        if(scores[i] != scores[i-1]){
            scores[j++] = scores[i];
        }
    }
    int size = scores.size();
    for(i = 0; i < size-j; i++){
        scores.pop_back();
    }
    vector<int> ranks;

    i = 0;
    j = scores.size()-1;
    while(i < alice.size()){
        if(j < 0){
            ranks.push_back(1);
            i++;
            continue;
        }
        if(alice[i] < scores[j]){
            ranks.push_back(j+2);
            i++;
        } else if(alice[i] > scores[j]){
            j--;
        } else {
            ranks.push_back(j+1);
            i++;
        }
    }

    return ranks;
}

I think this may help you too:

vector is like an array list that resizes itself.

push_back() is inserting at the end of the vector.

pop_back() is removing from the end of the vector.