2
\$\begingroup\$

I tried to solve the following challenge and optimize the solution but my code still times out. My code is below.

Problem statement

Climbing the Leaderbord

Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. The game uses Dense Ranking, so its leaderboard works like this:

  • The player with the highest score is ranked number 1 on the leaderboard.
  • Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number.

For example, the four players on the leaderboard have high scores of 100, 90, 90, and 80. Those players will have ranks 1, 2, 2, and 3, respectively. If Alice's scores are 70, 80 and 105, her rankings after each game are 4th, 3rd and 1st.

Function Description

Complete the climbingLeaderboard function in the editor below. It should return an integer array where each element \$res[j]\$ represents Alice's rank after the \$j^{th}\$ game.

climbingLeaderboard has the following parameter(s):

  • scores: an array of integers that represent leaderboard scores
  • alice: an array of integers that represent Alice's scores

Input Format

The first line contains an integer \$n\$, the number of players on the leaderboard. The next line contains \$n\$ space-separated integers \$scores[i]\$, the leaderboard scores in decreasing order. The next line contains an integer, \$m\$, denoting the number games Alice plays. The last line contains \$m\$ space-separated integers \$alice[j]\$, the game scores.

Constraints

  • \$1 \le n \le 2 \times 10^5\$
  • \$1 \le m \le 2 \times 10^5\$
  • \$0 \le scores[i] \le 10^9\$ for \$0 \le i \lt n\$
  • \$0 \le alice[j] \le 10^9\$ for \$0 \le j \lt m\$
  • The existing leaderboard, \$scores\$, is in descending order.
  • Alice's scores, \$alice\$, are in ascending order.

Subtask

For 60% of the maximum score:

  • \$1 \le n \le 200\$
  • \$1 \le m \le 200\$

Output Format

Print \$m\$ integers. The \$j^{th}\$ integer should indicate Alice's rank after playing the \$j^{th}\$ game.

From Climbing the Leaderboard on HackerRank.com.

My code

The code simply starts with climbingLeaderboard method below which delete all similar values in the scores array, after that it start with Alice score and using binary search it return the correct position.

int getPosition(vector<int> scores,int value,int start,int end){

    int middle = (start+end)/2;

    if(scores[start]<value){
        return start;
    }else if(scores[end]>value){
        return end+1;
    }

    else if(scores[middle]==value){
        return middle;
    }
    else if(start==end){
        if(scores[start]>value){
            return start+1;
        }else{
            return start;
        }
    }

    else if(scores[middle]>value){
        return getPosition(scores,value,middle+1,end);
    }else{
        return getPosition(scores,value,start,middle-1);
    }

}
/////
/////

vector<int> climbingLeaderboard(vector<int> scores, vector<int> alice) {

    int i=1;
    while(1){
        if(i == scores.size()){
            break;
        }
        if(scores[i]==scores[i-1]){
            scores.erase(scores.begin() + i);
            continue;
        }
        i++;
    }
    vector<int> results;
    int endValue = scores.size()-1;

    for(int j=0;j<alice.size();j++){
        endValue = getPosition(scores,alice[j],0,endValue);
        results.insert(results.end(),endValue+1);
    }

    return results;

    }

Any ideas? How can I make it not time out?

\$\endgroup\$
  • \$\begingroup\$ Also, it would be nice if the code can compile on its own, which requires the necessary #includes and other things (which I prefer not to guess). \$\endgroup\$ – L. F. Aug 16 at 21:16
1
\$\begingroup\$

\$\DeclareMathOperator{\Oh}{O}\$Frankly, the code in the HackerRank editor is a large mess. It is promoting crap like #include <bits/stdc++.h> and using namespace std;, and the code contains many problems: int for traversing a std::vector, copying containers around, etc. Not to mention bad practices like i++, explicitly calling fout.close(), not using standard algorithm, etc. It really shouldn't be like that.

In your code, the whole getPosition function is redundant. Use std::lower_bound instead. And since std::vector::erase is \$\Oh(n)\$, the code is \$\Oh(n^2)\$, which is unnecessary inefficient.

The problem is very simple and can be finished in several lines without sacrificing readability:

using score_t = long;
using rank_t = long;

// scores is passed by value to take advantage of possible optimization.
rank_t get_rank(std::vector<score_t> scores, score_t alice_score)
{
    scores.erase(std::unique(scores.begin(), scores.end()), scores.end());

    auto it = std::lower_bound(scores.begin(), scores.end(), alice_score, std::greater<>{});
    return it - scores.begin() + 1;
}

The code is \$\Oh(n)\$ and I don't think you can do better. Note that each score of Alice's is independent, so it makes no sense to process them together in a function. I used long because the problem seems to require numbers as large as \$10^9\$. scores will be modified in the function, so instead of making a copy manually, we let the compiler do so for us in the parameter list. This enables possible optimization opportunities.

Here, we used two standard algorithms:

  • std::unique, which "removes" adjacent equal elements. Standard algorithms cannot change the size of scores via iterators, so std::unique makes sure that the first \$N\$ elements are the result, where \$N\$ is the number of elements in the result. The rest of the elements are placed in a valid but otherwise unspecified state. Then, we call erase to erase these garbage elements. This is also known as the remove-erase idiom.

  • std::lower_bound, which performs a binary search and returns the first element that compares not "less" than the provided value. By default, "less" is defined by <, thus operating on an ascending sequence. In this case, we use std::greater<> to define "less" by >, so that std::lower_bound is adapted to work on a descending sequence.


Now let's go through your code: (regardless of whether the code is what hackerrank gives you)

int getPosition(vector<int> scores,int value,int start,int end){

As I said, this function is provided by the standard library and you shouldn't be reinventing your own without a good reason. If you want to see how the standard version looks like, there is an example implementation at cppreference.


vector<int> climbingLeaderboard(vector<int> scores, vector<int> alice) {

As I said before, this function is illogical. It should handle one Alice-score at a time. Also, climbingLeaderboard isn't really a good function name.

Passing scores by value is justified because you modify it in the functions, but passing alice by value introduces an unnecessary copy. It should be passed by const reference instead. And int is not only a magic type, but also a type that is not sufficiently large here.


int i=1;
while(1){
    if(i == scores.size()){
        break;
    }
    if(scores[i]==scores[i-1]){
        scores.erase(scores.begin() + i);
        continue;
    }
    i++;
}

Space. Also, I am not sure what you are trying to achieve with the while (1) loop here: you are obfuscating the code by refusing to place the condition in the proper place. And int isn't the correct type to use here. Use size_type (or at least a named type). ++i should be used instead of i++ in a discarded value expression.

And you are essentially reimplementing the \$\Oh(n)\$ std::unique in a \$\Oh(n^2)\$ way. Just use the standard algorithm and avoid reinventing the wheel.


vector<int> results;
int endValue = scores.size()-1;

In this particular case, we know that !scores.empty(), but storing the result in a int is still inadvisable. Use auto or std::vector<int>::size_type.


for(int j=0;j<alice.size();j++){
    endValue = getPosition(scores,alice[j],0,endValue);
    results.insert(results.end(),endValue+1);
}

Again, space. And ++j not j++. And the third line is just

results.push_back(endValue + 1);

There is no reason to use insert + iterator here.


    return results;

    }

Is the weird indentation a copy-paste problem?

\$\endgroup\$
  • \$\begingroup\$ Why Would i++ be Bad Practice? \$\endgroup\$ – Ryan Stone Aug 17 at 14:01
  • \$\begingroup\$ Since the vector given is sorted in descending order, lower_bound doesn't seem to work right. \$\endgroup\$ – tinstaafl Aug 18 at 3:46
  • \$\begingroup\$ @tinstaafl that's exactly when the generality and flexibility of STL comes to play -- in this case, you use greater. \$\endgroup\$ – L. F. Aug 18 at 8:33
  • 1
    \$\begingroup\$ @RyanStone Unless you need the pre-increment value, the copy involved is useless. And while that is harmless at least for small trivial types if the operation is inlined, it's a bad habit to have due to the compiler not being able to fix it for you in more complex cases, with less optimisation, or with insufficient information. \$\endgroup\$ – Deduplicator Aug 18 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.