# Easy Java Solution, Sorting.

• Basically this question is to find out the `score` -> `ranking` mapping. The easiest way is to sort those `scores` in `nums`. But we will lose their original order. We can create (`score` , `original index`) pairs and sort them by `score` decreasingly. Then we will have `score` -> `ranking` (new index) mapping and we can use `original index` to create the result.

Time complexity: O(NlgN). Space complexity: O(N). N is the number of scores.

``````Example:

nums[i]    : [10, 3, 8, 9, 4]
pair[i][0] : [10, 3, 8, 9, 4]
pair[i][1] : [ 0, 1, 2, 3, 4]

After sort:
pair[i][0] : [10, 9, 8, 4, 3]
pair[i][1] : [ 0, 3, 2, 4, 1]
``````
``````public class Solution {
public String[] findRelativeRanks(int[] nums) {
int[][] pair = new int[nums.length][2];

for (int i = 0; i < nums.length; 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];

for (int i = 0; i < nums.length; i++) {
if (i == 0) {
result[pair[i][1]] = "Gold Medal";
}
else if (i == 1) {
result[pair[i][1]] = "Silver Medal";
}
else if (i == 2) {
result[pair[i][1]] = "Bronze Medal";
}
else {
result[pair[i][1]] = (i + 1) + "";
}
}

return result;
}
}
``````

Also we can use an one dimension array. This will save a little bit space but space complexity is still O(n).

``````public class Solution {
public String[] findRelativeRanks(int[] nums) {
Integer[] index = new Integer[nums.length];

for (int i = 0; i < nums.length; i++) {
index[i] = i;
}

Arrays.sort(index, (a, b) -> (nums[b] - nums[a]));

String[] result = new String[nums.length];

for (int i = 0; i < nums.length; i++) {
if (i == 0) {
result[index[i]] = "Gold Medal";
}
else if (i == 1) {
result[index[i]] = "Silver Medal";
}
else if (i == 2) {
result[index[i]] = "Bronze Medal";
}
else {
result[index[i]] = (i + 1) + "";
}
}

return result;
}
}
``````

• Besides using a 2D array, you can also use another array to do sorting, with a map to map between the sorted array and the original array.

``````public class Solution {
public String[] findRelativeRanks(int[] nums) {
int[] ranks = nums.clone();
Arrays.sort(ranks);
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i<ranks.length; i++){
map.put(ranks[i], nums.length-i);
}
String[] res = new String[nums.length];
for(int i = 0; i<nums.length; i++){
int rank = map.get(nums[i]);
String rankStr = rank+"";
if(rank==1) rankStr = "Gold Medal";
else if(rank==2) rankStr = "Silver Medal";
else if(rank==3) rankStr = "Bronze Medal";
res[i] = rankStr;
}
return res;
}
}
``````

• good solution, use `nums.length - i` in map. I reverse the sorted Array....

• Arrays.sort(index, (a, b) -> (nums[b] - nums[a]));

This part is genius

• @Chidong yeah, it realize the Descending Sort. Soga.....

• Feels like the best solutions are either sort an array or use a priority queue.

• Python version:

``````class Solution(object):
def findRelativeRanks(self, nums):
mp = {}
as1 = list(nums)
as1.sort(reverse=True)
for k,v in enumerate(as1):
if k == 0:
mp[v] = "Gold Medal"
elif k == 1:
mp[v] = "Silver Medal"
elif k == 2:
mp[v] = "Bronze Medal"
else:
mp[v] = str(k + 1)
arr = []
for i in nums:
arr.append(mp[i])
return arr
``````

Javascript version:

``````var findRelativeRanks = function(nums) {
var ranks = nums.slice();
ranks.sort(function(a, b) {return a-b});
var mp = {}
for(var i = 0; i < ranks.length; i++) {
mp[ranks[i]] = nums.length-i;
}
var res = new Array(nums.length);
for(var i =0; i < nums.length; i++) {
var rank = mp[nums[i]]
var rankStr = rank + "";
if(rank==1) rankStr = "Gold Medal";
else if(rank == 2) rankStr = "Silver Medal";
else if (rank == 3) rankStr = "Bronze Medal";
res[i] = rankStr;
}
return res;
};
``````

Golang version:

``````import ("sort"
"strconv")

func findRelativeRanks(nums []int) []string {
ranks:=make([]int, len(nums))
copy(ranks, nums)
sort.Sort(ByInt(ranks));
mp := make(map[int]int)
for i := 0; i < len(ranks); i++ {
mp[ranks[i]] = len(nums)-i
}
res := make([]string, len(nums))
for i:=0; i < len(nums); i++ {
rank := mp[nums[i]]
rankStr := strconv.Itoa(rank)
if rank==1 { rankStr = "Gold Medal"

} else if rank == 2 {rankStr = "Silver Medal"

} else if rank == 3 {rankStr = "Bronze Medal" }
res[i] = rankStr
}
return res
}

type ByInt []int

func (a ByInt) Len() int           { return len(a) }
func (a ByInt) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByInt) Less(i, j int) bool { return a[i] < a[j] }

``````

• C++ version with a hash map: score -> index:

``````    vector<string> findRelativeRanks(vector<int>& nums) {
unordered_map<int, int> num2Idx; int i = 0;
for (int n : nums) num2Idx[n] = i++; // build map: num -> index
sort(nums.begin(), nums.end());

vector<string> rank(i), medals{"Gold Medal", "Silver Medal", "Bronze Medal"};
for (int n : nums) rank[num2Idx[n]] = i>3? to_string(i--) : medals[--i];
return rank;
}
``````

• Besides using a 2D array, you can also use another array to do sort, with a map to map between the sorted array and the original array.

``````        int[] ranks = nums.clone();
Arrays.sort(ranks);
``````

I think you could achieve the the same purpose without using an extra O(N) space to define array ranks[]. The hash map can be generated by nums and it doesn't matter in which order res[i] is assigned in terms of the index. Of course, your solution has the benefit not altering the original array nums[].

• @austurela take a look on my O(n) solution below

• In solution 2, why index has to be an Integer array instead of int array?

• @gogogoogle seems like we are talking about different solutions, here is the last one from me on this problem https://discuss.leetcode.com/topic/78588/java-6ms-solution-o-n-without-sorting

• @gogogoogle This is one of the shortcoming of Java `Arrays` class. It only support `public static <T> void sort(T[] a, Comparator<? super T> c)` The `T` here has to be an `Object`, can't be a primitive type.

https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-T:A-java.util.Comparator-

• @Chidong This is a best solution and easy to understand. map.get(i) returns the value of that key, which is nums[i]. clever trick to link rank[] and nums[]!

20ms for 17 test cases

• said in Easy Java Solution, Sorting.:

(a, b) -> (nums[b] - nums[a])

Can you clarify this detail? Are there any documentations for this "->" operator?

• @noboundaries It is called Lambda Expressions, introduced in Java 8. You can refer to http://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html
Basically it same as

``````Arrays.sort(index, new Comparator<Integer>{
@Override
public int compare(Integer a, Integer b){
return nums[b] - nums[a];
}
});

``````

• @Chidong Now it makes a lot more sense. Thank you so much for the prompt reply!

• @zzg_zzm
Using no extra space to clone the array.
Time: O(nlogn) -> Sorting
Space: O(n) -> HashMap

``````public class Solution {
public String[] findRelativeRanks(int[] nums) {
String[] result = new String[nums.length];
HashMap<Integer, Integer> map = new HashMap<>();
for (int i=0; i<nums.length; i++) {
map.put(nums[i], i);
}
Arrays.sort(nums);
for (int i=0; i<nums.length; i++) {
if (i == nums.length-1)
result[map.get(nums[i])] = "Gold Medal";
else if (i == nums.length-2)
result[map.get(nums[i])] = "Silver Medal";
else if (i == nums.length-3)
result[map.get(nums[i])] = "Bronze Medal";
else
result[map.get(nums[i])] = (nums.length - i)+"";
}
return result;
}
}``````

• Good solution!
In fact,i think we could use just one simple array to solve the question.For there will be no more than 10000 elements in the array, and that's my code

``````       public String[] findRelativeRanks(int[] nums) {
long[] sort = new long[nums.length];
for(int i=0;i<nums.length;i++){
sort[i]=nums[i]*10000+i;
}
Arrays.sort(sort);
String[] result = new String[nums.length];
for(int i=nums.length-1;i>=0;i--){
if(i==(nums.length-1)){
result[(int)(sort[i]%10000)]="Gold Medal";
}else if(i==(nums.length-2)){
result[(int)(sort[i]%10000)]="Silver Medal";
}else if(i==(nums.length-3)){
result[(int)(sort[i]%10000)]="Bronze Medal";
}else{
result[(int)(sort[i]%10000)]=(nums.length-i)+"";
}
}
return result;
}
``````

`sort[i]=nums[i]*10000+i;`
the order of sort is the same with thr origin arrays.Besides,we could `sort[i]%10000` to get the index in the origin array,

• Same strategy slightly concise

``````public class Solution {
private String[] medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};

public String[] findRelativeRanks(int[] nums) {
int len = nums.length;
String[] output = new String[len];

Map<Integer, Integer> reverseMap = new HashMap<>(len);

for(int i=0; i<len; i++) reverseMap.put(nums[i], i);

Arrays.sort(nums);

for(int i=len-1; i>-1; i--) output[reverseMap.get(nums[i])] = getText(len-i-1);

return output;

}

private String getText(int rank) {
return (rank < medals.length) ? medals[rank] : String.valueOf(rank+1);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.