Relative-Ranks.java

class Solution {
    public String[] findRelativeRanks(int[] score) {
        int maxVal = maxElement(score);
        int[] arr = new int[maxVal + 1];
        int N = score.length;

        for(int i = 0; i < N; i++){
            arr[score[i]] = i + 1;
        }

        String[] res = new String[N];

        int rank = 1;
        for(int i = maxVal; i >= 0; i--){
            if(arr[i] != 0){
                int index = arr[i] - 1;
                if(rank == 1){
                    res[index] = "Gold Medal";
                }
                else if(rank == 2){
                    res[index] = "Silver Medal";
                }
                else if(rank == 3){
                    res[index] = "Bronze Medal";
                }
                else{
                    res[index] = Integer.toString(rank);
                }
                rank++;
            }

            // Smaller Optimization
            if(rank > N){
                break;
            }
        }        
        return res;
    }

    public int maxElement(int[] score){
        int max = Integer.MIN_VALUE;
        for(int e : score){
            max = Math.max(max, e);
        }
        return max;
    }
}