# My 12ms O(n) solution in java

• Borrow the idea of Pigeonhole Sort, since the scores are UNIQUE, we can use a int[] array as a hash map map[] to store the score-index info. Then we traverse the array map[] in the descent order of scores, it will automatically sort score-index. For each score, we find its index map[i] in original array and assign that position in the original array nums[map[i]] as the ranking number j, which keeps adding 1 whenever it encounters a non-null element.
Since such sorting is not comparison based, it doesn’t have the O(nlogn) lower bound so it can be faster than most sorting methods.
TC: O(n+range) SC: O(range) where range is the range of ints in nums[], also it is the length of map[].
It is my first time to submit my answer, help leave comment if you have any suggestions or better ideas to help improve my post! :)

``````public String[] findRelativeRanks(int[] nums) {
int max = nums[0], min = nums[0];
for(int i=1, n = nums.length; i<n; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
int length = max - min +1;
Integer[] map = new Integer[length];
for(int i=0, n = nums.length; i<n; i++) {
map[max - nums[i]] = i;
}
String[] res = new String[nums.length];
System.out.println(Arrays.toString(map));
for (int i=0, j=0; i<length; i++){
if(map[i] == null) continue;
else {
if(j == 0) res[map[i]] = "Gold Medal";
else if(j == 1) res[map[i]] = "Silver Medal";
else if(j == 2) res[map[i]] = "Bronze Medal";
else res[map[i]] = j+1+"";
j++;
}
}
return res;
}
``````

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