Java - Time O(n*logn) Space O(n) Simple sorting.


  • 0
    B

    We need to sort the array to find the ranking.
    But after sorting, index will altered.
    So, original index is stored in a map.

    And is retrieved while preparing the answer string.

    public class Solution {
        public String[] findRelativeRanks(int[] nums) {
            
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            
            int len = nums.length;
            if(len == 0) {
                return new String[]{};
            }
            
            // Because of sorting, the original pair of number to index will be lost.
            // So, it has to be preserved in the form of a map.
            for(int i = 0; i< len; i++) {
                map.put(nums[i], i);
            }
            
            // Sort the array.
            Arrays.sort(nums);
            
            String [] ans = new String[len];
            
            // Hard coded strings.
            if(len >= 1) {
                ans[map.get(nums[len-1])] = "Gold Medal";
            }
            
            if(len >= 2) {
                ans[map.get(nums[len-2])] = "Silver Medal";
            }
        
            if(len >= 3) {
                ans[map.get(nums[len-3])] = "Bronze Medal";
            }
            
            
            // Prepare the ans.
            for(int i = len-4; i>= 0; i--) {
                
                // For the sorted array, find out its original rank.
                int rankForIndex = map.get(nums[i]);
                
                ans[rankForIndex] = "" + (len - i);
            }
            
            return ans;
            
        }
    }
    

Log in to reply
 

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