• + 0 comments

    Time complexity: O(n*log(n))

    Space complexity: O(n)

    Idea:

    1. Build the map to get the rank of each ranked_arr[i].
    2. Binary search to get the index of the player[i] insert into ranked_arr.
    3. Get the rank for player[i].
    int* build_ranked_arr(int length, int* arr){
        int rank = 1;
        int* res_arr = (int* )malloc(length*sizeof(int));
        res_arr[0] = rank;
        for (int i = 1; i<length; i++){
            if (arr[i] == arr[i-1]) res_arr[i] = res_arr[i-1];
            else{
                rank++;
                res_arr[i] = rank;
            } 
        }
        return res_arr;
    }
    
    int binary_search_find_left_index(int length, int* arr, int target){
        int l = 0, r = length-1;
        while (l <= r){
            int m = (l+r)/2;
            if (arr[m] > target) l = m+1;
            else r = m-1;
        }
        return l;
    }
     
    int* climbingLeaderboard(int ranked_count, int* ranked, int player_count, int* player, int* result_count) {
        int* ranked_arr = (int* )malloc(ranked_count*sizeof(int));
        int* res_arr = (int* )malloc(player_count*sizeof(int));
        *result_count = player_count;
        ranked_arr = build_ranked_arr(ranked_count, ranked);
        for (int i = 0; i<player_count; i++){
            int temp_index = binary_search_find_left_index(ranked_count, ranked, player[i]);
            if (temp_index == 0) res_arr[i] = 1;
            else{
                res_arr[i] = ranked_arr[temp_index-1]+1;
            }
        }
        return res_arr;
    }