Relative Ranks

Problem

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal".

Example 1:
Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". 
For the left two athletes, you just need to output their relative ranks according to their scores.

Note:

• N is a positive integer and won't exceed 10,000.
• All the scores of athletes are guaranteed to be unique.

Solution

Solution Using HashMap: O(n) time and O(n) space

public class Solution {
    public String[] findRelativeRanks(int[] nums) {
        if (nums == null || nums.length == 0) return new String[] {};
        int[] ranks = nums.clone();
        Arrays.sort(ranks); //Cannot sort primitive array using Comparator 

        Map<Integer, String> map = new HashMap<>();
        int len = nums.length;
        if (len >= 1) map.put(ranks[len - 1], "Gold Medal");
        if (len >= 2) map.put(ranks[len - 2], "Silver Medal");
        if (len >= 3) map.put(ranks[len - 3], "Bronze Medal");
        for (int i = 4; i <= len; i++) map.put(ranks[len - i], i + "");

        String[] res = new String[len];
        for (int i = 0; i < len; i++) res[i] = map.get(nums[i]);
        return res;
    }
}

Optimal Space Solution: O(n) time and O(1) space

public class Solution {
    public String[] findRelativeRanks(int[] nums) {
        if (nums == null || nums.length == 0) return new String[] {};
        int len = nums.length;
        Integer[] indices = new Integer[len]; //To be able to use Comparator, we init with type Integer
        for (int i = 0; i < len; i++) indices[i] = i;
        Arrays.sort(indices, (a, b) -> nums[b] - nums[a]); //Key step in this solution!
        String[] res = new String[len];
        for (int i = 0; i < len; i++) {
            int index = indices[i];
            if (i == 0) res[index] = "Gold Medal";
            else if (i == 1) res[index] = "Silver Medal";
            else if (i == 2) res[index] = "Bronze Medal";
            else res[index] = (i + 1) + "";
        }
        return res;
    }
}

Analysis

The idea in both solutions is to first get the rank of given nums
Then return ranks in correct position
The first solution uses a HashMap to store the rank in required format
Map's key is the score in nums, value is the rank
Then we loop the result from beginning and fill the rank by map.get(nums[i])

While in the optimal space solution, we use array indices to make it constant space
We first fill 1 to n as index for the nums in indices
Then we sort the indices by (a, b) -> nums[b] - nums[a]
Therefore the indices becomes the index of ranked nums
For example, nums = [8, 6, 10], indices is init with [0, 1, 2]
After the sorting, indices becomes [2, 0, 1]
So the last for loop makes sense to create the correct result