Reduce execution time of a code that uses binary search

Question

The problem is to create an array of player ranks based on 2 other arrays: leaderboard and player scores. More explanations of the problem here: https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem.

The code below is a spaghetti but it's working fine. But, for large size of ranked array(200000 elements for example), it times out. I'm not asking for code to copy/paste. I just wanna know if there is a way to optimize this code.


int* climbingLeaderboard(int ranked_count, int* ranked, int player_count, int* player, int* result_count) {
    
    *result_count=player_count;
    // remove duplicates
    int removed=0;
    for(int i=0, j=1; i<ranked_count-removed; i++, j++){   
      if(ranked[i]==ranked[j]){
        for(int k=j; k<ranked_count-removed; k++) 
           ranked[k]=ranked[k+1]; 
        removed++;
      }
    }
    int newsize=ranked_count-removed;
    // create an array to store ranks then fill it
    int* positions=malloc(newsize*sizeof(int));
    positions[0]=1;
    for(int i=0, j=1; j<newsize; i++, j++){
        positions[j]=(ranked[j]<ranked[i])? (positions[i]+1) : positions[i];
    }
    // create and fill the results array using binary search
    int* res = malloc(player_count*sizeof(int));
    int start=0, end=newsize-1, middle=(start+end)/2;
    int j, k=newsize-1;
    for(int i=0; i<player_count; i++){
        if(i>0&&player[i]==player[i-1]){
            *(res+i)=(*(res+(i-1))); 
            continue;
        }
        if(player[i]>=ranked[middle]){
            *(res+i)=positions[middle]; 
            j=middle-1;
            while(j>=0){
                if(player[i]>=ranked[j]) 
                    *(res+i)=positions[j];
                else if(j==k) 
                    *(res+i)=positions[j]+1; 
                else break; 
                --j;
            }
            start=0; end=middle-1;
        }
        else{
            *(res+i)=positions[newsize-1]+1; 
            j=newsize-1;
            while(j>=middle){
                if(player[i]>=ranked[j]) 
                    *(res+i)=positions[j];
                else if(j==k) 
                    *(res+i)=positions[j]+1; 
                else break; 
                --j;
            }
            start=middle+1; end=newsize-1;
        }
        middle=(start+end)/2;
    }
    free(positions);
    return res;
}

Get out of the habit of using *(res+i). This is equivalent to res[i] and the latter is generally considered easier to read and understand. — Barmar
– Barmar, Commented Jan 31, 2023 at 21:59
The enter key is your friend. It will be easier for you to follow the flow of your own code (and find problems with it) if you don’t put as much as possible on single lines. If you put braces on their own lines and a newline after every semicolon your code will be significantly more readable. — 44stonelions
– 44stonelions, Commented Jan 31, 2023 at 22:00
I'm not going to create an account on HackerRank to read the description of the problem you're trying to sole and the constraints on the input. That belongs in the question here. — Retired Ninja
– Retired Ninja, Commented Jan 31, 2023 at 22:03
@redone_lsf But if no one can read your code, no one can help you. — Steve Summit
– Steve Summit, Commented Jan 31, 2023 at 22:11
@redone_lsf: I would advise you to change this approach: readable code helps solve the problem. Cramming statements on the same line causes hard to find bugs. The space bar is your friend — chqrlie
– chqrlie, Commented Jan 31, 2023 at 22:12

chqrlie · Accepted Answer · 2023-01-31 23:33:54Z

The initial loop to remove duplicates has a potential quadratic time complexity. You can achieve linear complexity using the 2 finger approach:

    int removed = 0;
    for (int i = 1, j = 1; j < ranked_count; j++) {
        if (ranked[i - 1] != ranked[j])
            ranked[i++] = ranked[j];
        else
            removed++;
    }

More generally, the argument arrays should not be changed in spite of the sloppy prototype given:

int *climbingLeaderboard(int ranked_count, int *ranked,
                         int player_count, int *player,
                         int *result_count);

Here are simple steps I would recommend to solve this problem:

allocate and initialize a ranking array with the ranking for each of the scores in the ranked array. Be careful to allocate ranked_count + 1 elements.
allocate a result array res of length player_count, set the result_count to player_count.
starting with pos = ranked_count, for each entry i in player:
- locate the position pos where the entry would be inserted in the ranking array using binary search between position 0 and the current pos inclusive. Make sure you find the smallest entry in case of duplicate scores.
- set res[i] to ranking[pos]
free the ranking array
return the res array.

Here is a simple implementation:

int *climbingLeaderboard(int ranked_count, int *ranked,
int player_count, int *player,
int *result_count)
{
if (player_count <= 0) {
*result_count = 0;
return NULL;
}
int *ranking = malloc(sizeof(*ranking) * (ranked_count + 1));
int rank = 1;
ranking[0] = rank;
for (int i = 1; i < ranked_count; i++) {
if (ranked[i] != ranked[i - 1])
rank++;
ranking[i] = rank;
}
ranking[ranked_count] = rank + 1;

int *res = malloc(sizeof(*res) * player_count);
*result_count = player_count;

int pos = ranked_count;
for (int i = 0; i < player_count; i++) {
int start = 0;
while (start < pos) {
int middle = start + (pos - start) / 2;
if (ranked[middle] > player[i])
start = middle + 1;
else
pos = middle;
}
res[i] = ranking[pos];
}
free(ranking);
return res;
}

user17592432 · Accepted Answer · 2023-01-31 22:36:09Z

0

Look for ways to use "branchless" to improve execution speed:

    positions[0]=1;
    for(int i=0, j=1; j<newsize; i++, j++){
        positions[j]=(ranked[j]<ranked[i])? (positions[i]+1) : positions[i];
    }

becomes

    positions[0] = 1;
    for( int i = 0, j = 1; j < newsize; i++, j++ )
        positions[j] = positions[i] + (ranked[j] < ranked[i]);

Other than this, I don't even want to try to sort out what this code is attempting.

answered Jan 31, 2023 at 22:36

user17592432

Collectives™ on Stack Overflow

Reduce execution time of a code that uses binary search

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related