algoadvance

Leetcode 506. Relative Ranks

Problem Statement

You are given an integer array score of size n, where score[i] is the score of the i-th athlete in a competition. You need to rank the athletes based on their scores. The athletes with the highest scores get ranks “Gold Medal”, “Silver Medal”, and “Bronze Medal”, respectively. Other athletes get their ranks in descending order of their scores, starting from 4th place.

Write a function findRelativeRanks that returns a list of strings where each string represents the rank of the respective athlete.

Clarifying Questions

  1. Q: Are there any constraints on the size of the score array? A: The array size will be between 1 and 10^4.

  2. Q: Can the scores be negative? A: Typically, scores in competitions are non-negative. However, if scores can be negative, the problem still treats them in the same relative way.

  3. Q: How should ties in scores be handled? A: For this problem, there are no ties in the scores. Each score is unique.

Strategy

  1. Sort the Scores:
    • First, we need to sort the scores in descending order. To retain original indices, we use a list of pairs (score, index).
  2. Assign Medals and Ranks:
    • Create an array to store the results.
    • Assign special ranks (“Gold Medal”, “Silver Medal”, “Bronze Medal”) for the top three athletes.
    • Assign ordinal ranks starting from 4th place for the rest.
  3. Map Ranks to Original Indices:
    • Iterate over the sorted list of scores, and assign the appropriate rank to the corresponding original index in the result array.

Code

Here is a solution in Java:

import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    public String[] findRelativeRanks(int[] score) {
        int n = score.length;
        String[] result = new String[n];
        
        // Pairing scores with their indices
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        // Sorting indices based on the scores, in descending order
        Arrays.sort(indices, (a, b) -> score[b] - score[a]);
        
        // Assigning ranks based on sorted order
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                result[indices[i]] = "Gold Medal";
            } else if (i == 1) {
                result[indices[i]] = "Silver Medal";
            } else if (i == 2) {
                result[indices[i]] = "Bronze Medal";
            } else {
                result[indices[i]] = String.valueOf(i + 1);
            }
        }
        
        return result;
    }
}

Time Complexity

Thus, the overall time complexity of the solution is O(n log n). This is efficient, given the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI