algoadvance

Leetcode 506. Relative Ranks

Problem Statement

You are given an integer array score of size n, where score[i] represents the score of the i-th athlete. The ranks are assigned as follows:

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

Example

Input: score = [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Input: score = [10, 3, 8, 9, 4]
Output: ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

Clarifying Questions

  1. Q: Should the relative ranks be returned as strings? A: Yes, the ranks should be returned as strings, with the top three being specific labels (“Gold Medal”, “Silver Medal”, “Bronze Medal”) and the rest as numeric strings.

  2. Q: Are there any constraints on the input array size? A: The problem does not specify constraints, but typically for such problems, you can expect n to be within the range of (1 \leq n \leq 10^4).

  3. Q: Can scores be repeated? A: The problem statement does not specify unique scores, so we can assume they can be repeated.

  4. Q: Is the input array score guaranteed to have at least 1 element? A: Considering standard constraints and examples, yes, the array will have at least one element.

Strategy

  1. Create a vector of pairs, where each pair consists of a score and its original index.
  2. Sort the vector of pairs in descending order based on the score values.
  3. Traverse the sorted vector and assign appropriate ranks/mendals based on their positions.

Time Complexity

Thus, the overall time complexity is (O(n \log n)).

Code

Here’s the C++ code to solve the problem:

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<string> findRelativeRanks(vector<int>& score) {
    int n = score.size();
    vector<pair<int, int>> score_with_index;
    
    // Store scores with their original indices
    for(int i = 0; i < n; i++) {
        score_with_index.push_back({score[i], i});
    }
    
    // Sort scores in descending order
    sort(score_with_index.begin(), score_with_index.end(), [](pair<int, int>& a, pair<int, int>& b) {
        return b.first < a.first;
    });
    
    vector<string> result(n);
    
    for(int i = 0; i < n; i++) {
        int index = score_with_index[i].second;
        if (i == 0) {
            result[index] = "Gold Medal";
        } else if (i == 1) {
            result[index] = "Silver Medal";
        } else if (i == 2) {
            result[index] = "Bronze Medal";
        } else {
            result[index] = to_string(i + 1);
        }
    }
    
    return result;
}

This solution leverages sorting and indexing to ensure the relative ranks are assigned accurately and efficiently.

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