Relative Ranks Leetcode Solution

Difficulty Level Easy
Frequently asked in Google
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions SortingViews 5116

The problem Relative Ranks Leetcode Solution asks us to return a vector or an array of strings representing the relative ranks. We are provided with an array that represents the score obtained by athletes. Then we use the given score array to assign the ranks. There is a small change for the top 3 candidates. Instead of, assigning them simple numbers 1, 2, or 3. We need to assign Gold, Silver, and Bronze medal. Other than the top 3 candidates, we can assign them simple numbers from 4 to n. Let’s take a look at a few examples.

Relative Ranks Leetcode Solution

[1, 2, 3]
["Bronze Medal", "Silver Medal", "Gold Medal"]

Explanation: Since the given array represents the scores attained by the athletes. The athlete with the highest score will be given Gold Medal and so forth. Thus we gave Gold Medal to the athlete with a score of 3, Silver Medal to the athlete with a score of 2, and Bronze medal to the athlete with a score of 1.

[5, 4, 3, 2, 1]
["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Explanation: Since the top 3 candidates are awarded medals and the rest candidates are assigned a rank. Thus we have assigned medals to the top 3 candidates, and assigned rank 4, and 5 to the corresponding candidates.

Approach

The problem Relative Ranks Leetcode Solution asks us to assign the medals to the top 3 candidates and assign the ranks to the rest of the candidates. The simplest thing one can think of is to sort the given sequence. But we need to assign the ranks to the original indices. So, if we sort the given sequence directly, then we will miss the original indices. And will not be able to decide to assign the ranks. Thus to make sure that we do not lose the original indices, we create a new vector or array that stores the original indices with the scores. We sort this new array or vector. After sorting, we just assign the Gold, Silver, and Bronze medal to the corresponding candidates and ranks from 4 to n, to the deserving candidates. We can do this because when we sort our new modified array or vector, the original indices also swap their positions corresponding to the values stored.

Code for Relative Ranks Leetcode Solution

C++ code for Relative Ranks Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

vector<string> findRelativeRanks(vector<int>& nums) {
    vector<pair<int,int>> temp;
    int n = nums.size();
    for(int i=0;i<n;i++){
        temp.push_back(make_pair(nums[i], i));
    }
    sort(temp.rbegin(), temp.rend());
    vector<string> answer(n);
    answer[temp[0].second] = "Gold Medal";
    if(n>=2){
        answer[temp[1].second] = "Silver Medal";
    }
    if(n>=3){
        answer[temp[2].second] = "Bronze Medal";
    }
    for(int i=3;i<n;i++)
        answer[temp[i].second] = to_string(i+1);
    return answer;
}

int main(){
    vector<int> nums = {5, 4, 3, 2, 1};
    vector<string> answer = findRelativeRanks(nums);
    for(auto x: answer)cout<<x<<" ";
}

Gold Medal Silver Medal Bronze Medal 4 5

Java code Relative Ranks Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
  
    public static String[] findRelativeRanks(int[] nums) {
        int n = nums.length;
        int[][] pair = new int[nums.length][2];
        for (int i = 0; i < n; i++) {
            pair[i][0] = nums[i];
            pair[i][1] = i;
        }
        
        Arrays.sort(pair, (a, b) -> (b[0] - a[0]));
        
        String[] result = new String[nums.length];
        result[pair[0][1]] = "Gold Medal";
        if(n>=2)
            result[pair[1][1]] = "Silver Medal";
        if(n>=3)
            result[pair[2][1]] = "Bronze Medal";
        for (int i = 3; i < nums.length; i++) {
            result[pair[i][1]] = Integer.toString(i+1);
        }

        return result;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] nums = {5, 4, 3, 2, 1};
    String[] answer = findRelativeRanks(nums);
    for(int i=0;i<5;i++)
      System.out.print(answer[i] + " ");
  }
}
Gold Medal Silver Medal Bronze Medal 4 5

Complexity Analysis

Time Complexity

O(NlogN), because the sorting requires O(NlogN) time, where N is the number of elements ion the vector or array being sorted.

Space Complexity

O(NlogN), since we have used sorting that takes O(NlogN) space. The space complexity is also the same as time complexity.

Translate »