We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Climbing the Leaderboard
  5. Discussions

Climbing the Leaderboard

  • ryyaswanthraj
     + 0 comments

    Remove duplicates from rank array, use binary search to find closest number to the new alice score. time complexity O(n + mlogn) :)

    int binarySearch(int* ranked, int ranked_count, int cur_rank)
{
    int l=0;
    int r=ranked_count-1;
    int m;
    
    while (l<=r)
    {
        m = l + (r-l)/2;
    
        if (ranked[m] == cur_rank)
        {
            return m+1;
        }
        else if (ranked[m] > cur_rank)
        {
            l = m + 1;
        }
        else if (ranked[m] < cur_rank)
        {
            r = m - 1;
        }
    }
    
    return l+1;
}

int* climbingLeaderboard(int ranked_count, int* ranked, int player_count, int* player, int* result_count) {
    int* ranked_opt = (int*)malloc(sizeof(int) * ranked_count);
    int len = 0;
    for (int i=0; i<ranked_count; i++)
    {
        if (len != 0 && ranked[i] == ranked_opt[len-1]) continue;
        ranked_opt[len++] = ranked[i];
    }
    int* alice_rank = (int*)malloc(sizeof(int) * player_count);
    *result_count = 0;
    alice_rank[0] = 1;
    
    for (int i=0; i<player_count; i++)
    {
        alice_rank[(*result_count)++] = binarySearch(ranked_opt, len, player[i]);
    }
    
    return alice_rank;
}