Relative Ranks

Easy

Asked by:

31 views

Topics:

Arrays

You are given an integer array score of size n, where score[i] is the score of the i^th athlete in a competition. All the scores are guaranteed to be unique.

The athletes are placed based on their scores, where the 1^st place athlete has the highest score, the 2^nd place athlete has the 2^nd highest score, and so on. The placement of each athlete determines their rank:

The 1^st place athlete's rank is "Gold Medal".
The 2^nd place athlete's rank is "Silver Medal".
The 3^rd place athlete's rank is "Bronze Medal".
For the 4^th place to the n^th place athlete, their rank is their placement number (i.e., the x^th place athlete's rank is "x").

Return an array answer of size n where answer[i] is the rank of the i^th athlete.

Example 1:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1^st, 2^nd, 3^rd, 4^th, 5^th].

Example 2:

Input: score = [10,3,8,9,4]
Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
Explanation: The placements are [1^st, 5^th, 3^rd, 2^nd, 4^th].

Constraints:

n == score.length
1 <= n <= 10⁴
0 <= score[i] <= 10⁶
All the values in score are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `score`?
Can the elements in the `score` array be negative or zero?
Can there be duplicate scores in the input array, and if so, how should the ranks be assigned to athletes with the same score?
Is the input array guaranteed to be non-empty?
Beyond the top 3, is there a specific format required for representing ranks (e.g., can I assume the rank will always be a string representation of an integer)?

Brute Force Solution

Approach

To figure out the relative ranks, we can check every possible ordering of the scores. We will go through each score and compare it with every other score to determine its rank and give it the appropriate medal or rank number.

Here's how the algorithm would work step-by-step:

First, consider each score one by one.
For each score, compare it to every other score to count how many scores are higher.
Based on the count, determine the rank of the current score.
If the rank is 1, assign the score the Gold Medal.
If the rank is 2, assign the score the Silver Medal.
If the rank is 3, assign the score the Bronze Medal.
For all other ranks, assign the score its rank number as a string.

Code Implementation

def relative_ranks_brute_force(scores):
    result = []
    for current_score in scores:
        rank = 1
        # Determine the rank by comparing with other scores
        for other_score in scores:

            if other_score > current_score:
                rank += 1

        # Assign medals based on rank
        if rank == 1:
            result.append("Gold Medal")
        elif rank == 2:
            result.append("Silver Medal")
        elif rank == 3:
            result.append("Bronze Medal")
        else:
            result.append(str(rank))

    return result

Big(O) Analysis

Time Complexity

O(n²) – The provided approach iterates through each of the n scores in the input array. For each score, it compares it with every other score to determine its rank. This comparison involves another iteration of (n-1) scores in the worst case. Thus, the nested loop structure results in approximately n * (n-1) comparisons. This simplifies to n² - n, and as n grows, the n² term dominates, leading to a time complexity of O(n²).

Space Complexity

O(N) – The algorithm implicitly creates a new list or array to store the final results containing the medals or rank strings for each score. Since the number of scores to be ranked is N, where N is the number of input scores, this results list requires space proportional to N. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The key idea is to figure out who the top three performers are first. Then, instead of ranking everyone individually, we only need to handle the top three specially and rank the rest numerically.

Here's how the algorithm would work step-by-step:

First, make a copy of all the scores so we don't change the original list.
Then, sort the copied scores from highest to lowest. This lets us easily find the top scores.
Next, create a way to store the final rankings for each original score.
Now, go through the sorted list of scores. Assign "Gold Medal" to the highest score, "Silver Medal" to the second highest, and "Bronze Medal" to the third highest.
For all the other scores (below the top three), assign their rank as a regular number based on their position in the sorted list.
Finally, go back to the original list of scores. For each score, look up its corresponding rank that we stored earlier and return the final ranking list.

Code Implementation

def relative_ranks(scores):
    copied_scores = sorted(scores, reverse=True)

    # Store the rank for each score to easily retrieve later.
    score_to_rank = {}
    rankings = [""] * len(scores)

    for i, score in enumerate(copied_scores):
        if i == 0:
            score_to_rank[score] = "Gold Medal"
        elif i == 1:
            score_to_rank[score] = "Silver Medal"
        elif i == 2:
            score_to_rank[score] = "Bronze Medal"
        else:
            score_to_rank[score] = str(i + 1)

    # Assign the correct rank to the original scores
    for i, score in enumerate(scores):
        rankings[i] = score_to_rank[score]

    return rankings

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the copied scores, which takes O(n log n) time where n is the number of scores. Creating the copy and the result array takes O(n) time. Assigning ranks and retrieving ranks using the original array are both O(n) operations. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The algorithm creates a copy of the input scores array, resulting in an auxiliary array of size N, where N is the number of scores. A hash map (or similar data structure) is also used to store the final rankings for each original score, which will also hold at most N entries. Therefore, the dominant space usage is proportional to the input size N.

Edge Cases

Case	How to Handle
Empty or null input array	Return an empty array to indicate no rankings are possible.
Input array with only one element	Return an array with a single element 'Gold Medal'.
Input array with two elements	Return an array containing either 'Gold Medal', 'Silver Medal' or 'Silver Medal', 'Gold Medal' based on relative values.
Input array with three elements	Handle the Gold, Silver, and Bronze medals assignment correctly based on their relative order.
Input array with a large number of elements (performance scaling)	Ensure the sorting algorithm used has good average-case time complexity (e.g., O(n log n)).
Input array contains duplicate scores	The ranking logic should assign the same rank to duplicate scores, following the problem description of the 4th highest score receiving rank '4'.
Input array contains very large score values (integer overflow)	Use appropriate data types (e.g., long) to prevent integer overflow during calculations or comparisons.
Input array contains all identical score values	Assign the same rank (rank '4') to all athletes after assigning the top 3 ranks as best as possible

Empty or null input array

How to Handle:

Return an empty array to indicate no rankings are possible.

Input array with only one element

How to Handle:

Return an array with a single element 'Gold Medal'.

Input array with two elements

How to Handle:

Return an array containing either 'Gold Medal', 'Silver Medal' or 'Silver Medal', 'Gold Medal' based on relative values.

Input array with three elements

How to Handle:

Handle the Gold, Silver, and Bronze medals assignment correctly based on their relative order.

Input array with a large number of elements (performance scaling)

How to Handle:

Ensure the sorting algorithm used has good average-case time complexity (e.g., O(n log n)).

Input array contains duplicate scores

How to Handle:

The ranking logic should assign the same rank to duplicate scores, following the problem description of the 4th highest score receiving rank '4'.

Input array contains very large score values (integer overflow)

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during calculations or comparisons.

Input array contains all identical score values

How to Handle:

Assign the same rank (rank '4') to all athletes after assigning the top 3 ranks as best as possible