Sponsored
Sponsored
The idea is to sort the scores but preserve their original indices by pairing each score with its index. Once sorted, we can easily determine their ranks by iterating over the sorted list. We then assign the corresponding rank values based on their positions (i.e., 'Gold Medal' for the first position, etc.). This approach utilizes additional space to maintain the original indices while sorting the scores.
Time Complexity: O(n log n), where n is the number of scores, for the sorting operation.
Space Complexity: O(n) for storing the pair struct array and the result array.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6vector<string> findRelativeRanks(vector<int>& score) {
7 int n = score.size();
8 vector<pair<int, int>> scoreIndex;
9 for (int i = 0; i < n; ++i) {
10 scoreIndex.push_back({score[i], i});
11 }
12
13 sort(scoreIndex.rbegin(), scoreIndex.rend());
14
15 vector<string> result(n);
16 for (int i = 0; i < n; ++i) {
17 if (i == 0) result[scoreIndex[i].second] = "Gold Medal";
18 else if (i == 1) result[scoreIndex[i].second] = "Silver Medal";
19 else if (i == 2) result[scoreIndex[i].second] = "Bronze Medal";
20 else result[scoreIndex[i].second] = to_string(i + 1);
21 }
22
23 return result;
24}
25This C++ solution stores scores along with their indices in pairs. The sort function with reverse iterators is used to sort scores in descending order. We then assign ranks based on their sorted order, utilizing the original indices to place results back in order. Top three scores get special ranks 'Gold Medal', 'Silver Medal', and 'Bronze Medal'.
In this approach, we employ a hash map (or dictionary) to map each score to its ranking position in a sorted list. The scores are first sorted to determine order-based ranks. We then iterate through original scores, using the map to quickly assign the appropriate ranking (medal or numeric) to each score.
Time Complexity: O(n log n) from sorting.
Space Complexity: O(n) due to storage of the sorted copy.
1
This Python solution builds a mapping of each score to its ranking position from a sorted list of scores. Using a dictionary, ranks are quickly accessed and converted to medals where appropriate. This method effectively isolates rank determination from subsequent placement in the result.