You are viewing a single comment's thread. Return to all comments →
Time complexity: O(n*log(n))
Space complexity: O(n)
Idea:
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; }
Seems like cookies are disabled on this browser, please enable them to open this website
Climbing the Leaderboard
You are viewing a single comment's thread. Return to all comments →
Time complexity: O(n*log(n))
Space complexity: O(n)
Idea: