Relative Ranks - Practice Coding Problems

Relative Ranks - Problem

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 1st place athlete has the highest score, the 2nd place athlete has the 2nd highest score, and so on. The placement of each athlete determines their rank:

The 1st place athlete's rank is "Gold Medal"
The 2nd place athlete's rank is "Silver Medal"
The 3rd place athlete's rank is "Bronze Medal"
For the 4th place to the nth 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.

Input & Output

Example 1 — Basic Ranking

$ Input: score = [5,4,3,2,1]

› Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]

💡 Note: Score 5 is highest (Gold), 4 is second (Silver), 3 is third (Bronze), 2 gets rank "4", 1 gets rank "5"

Example 2 — Unordered Scores

$ Input: score = [10,3,8,9,4]

› Output: ["Gold Medal","5","Silver Medal","Bronze Medal","4"]

💡 Note: 10 is highest (Gold at index 0), 9 is second (Bronze at index 3), 8 is third (Silver at index 2), 4 gets "4", 3 gets "5"

Example 3 — Minimum Size

$ Input: score = [1]

› Output: ["Gold Medal"]

💡 Note: Single athlete automatically gets first place and Gold Medal

Constraints

1 ≤ score.length ≤ 10⁴
0 ≤ score[i] ≤ 10⁶
All values in score are unique

Visualization

Tap to expand

Understanding the Visualization

Input Scores

Array of athlete scores in original order

Rank by Performance

Determine placement: highest=1st, second=2nd, etc.

Assign Awards

Convert ranks to medals (top 3) or numbers (4th+)

Key Takeaway

🎯 Key Insight: Sort scores with index tracking to efficiently assign ranks while preserving original order

Asked in

a Amazon 15 G Google 8 M Microsoft 6

The key insight is to maintain the mapping between scores and their original positions while ranking. The optimal approach uses sorting with index tracking to achieve O(n log n) time complexity, efficiently assigning medals to top 3 and numeric ranks to others.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Count Better Scores	O(n²)	O(1)	For each athlete, count how many others scored higher to determine rank
Max Heap Approach	O(n log n)	O(n)	Use max heap to efficiently extract athletes in rank order
Sort with Index Tracking	O(n log n)	O(n)	Sort scores with their original indices, assign ranks, then restore original order

Brute Force - Count Better Scores — Algorithm Steps

For each athlete's score
Count how many other scores are higher
Rank = count + 1, convert to medal or number string

Visualization

Tap to expand

Step-by-Step Walkthrough

For Each Athlete

Compare their score against all others

Count Higher

Count how many scores are better

Assign Rank

Rank = count + 1, convert to medal or number

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char** solution(int* score, int n) {
    char** result = (char**)malloc(n * sizeof(char*));
    
    for (int i = 0; i < n; i++) {
        int rank = 1;
        for (int j = 0; j < n; j++) {
            if (score[j] > score[i]) {
                rank++;
            }
        }
        
        result[i] = (char*)malloc(20 * sizeof(char));
        if (rank == 1) {
            strcpy(result[i], "Gold Medal");
        } else if (rank == 2) {
            strcpy(result[i], "Silver Medal");
        } else if (rank == 3) {
            strcpy(result[i], "Bronze Medal");
        } else {
            sprintf(result[i], "%d", rank);
        }
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int score[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ' ') {
            score[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    char** result = solution(score, n);
    printf("[");
    for (int i = 0; i < n; i++) {
        if (i > 0) printf(",");
        printf("\"%s\"", result[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: for each of n athletes, check all n scores

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables, result array doesn't count as extra space

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Count Better Scores — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler