Relative Ranks: an NLogN solution

Problem comes from LeetCode: https://leetcode.com/problems/relative-ranks/, or copied/pasted:

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal".
Example 1:
Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". 
For the left two athletes, you just need to output their relative ranks according to their scores.
Note:
  1. N is a positive integer and won't exceed 10,000.
  2. All the scores of athletes are guaranteed to be unique.
My solution is an NLogN one. Here is the approach:
  • Create a mapping between the (unique) numbers and their indexes
  • Sort the array (hence the NLogN)
  • Go thru it (back-to-front) and do some minor logic to stamp the output properly
Not the fastest (beats only 8% of the C# submissions), but acceptable. Cheers, Marcelo.

    public class Solution
    {
        public string[] FindRelativeRanks(int[] nums)
        {
            if (nums == null || nums.Length == 0) return new string[0];

            Hashtable numToIndex = new Hashtable();
            for (int i = 0; i < nums.Length; i++)
            {
                numToIndex.Add(nums[i], i);
            }
            Array.Sort(nums);

            string[] ret = new string[nums.Length];
            string[] medals = { "Gold Medal", "Silver Medal", "Bronze Medal" };
            int position = 0;

            for (int i = nums.Length - 1; i >= 0; i--, position++)
            {
                ret[(int)numToIndex[nums[i]]] = (position < medals.Length) ? medals[position] : (position + 1).ToString();
            }

            return ret;
        }
    }

Comments

  1. Sleek! I usually use a parallel array of indices, which I sort based on the values of the nums array. This way we can save some memory (hashtable needs >2X memory) and cycles (the lookup is simply an array index operation).

    class Solution {
    public:
    vector findRelativeRanks(const vector& nums) {
    vector positions(nums.size());
    iota(positions.begin(), positions.end(), 0);
    sort(positions.begin(), positions.end(), [&](int i1, int i2) { return nums[i2] < nums[i1]; });
    vector result(nums.size());
    const array medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
    for (int i = 0; i < nums.size(); ++i) {
    result[positions[i]] = i < medals.size() ? medals[i] : to_string(i + 1);
    }
    return result;
    }
    };

    Thanks for sharing your solution!

    ReplyDelete
  2. BTW, this problem looks very similar to count sort:

    class Solution {
    public:
    vector findRelativeRanks(const vector& nums) {
    int highest = *max_element(nums.cbegin(), nums.cend());
    vector counts(highest+1, 0);
    for (int num : nums) counts[num] += 1;
    partial_sum(counts.begin(), counts.end(), counts.begin());
    vector result;
    const array medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
    for (int num : nums) {
    int place = nums.size() - counts[num];
    result.push_back(place < medals.size() ? medals[place] : to_string(place + 1));
    }
    return result;
    }
    };

    this solution beats 94% of other submissions in C++ :)

    ReplyDelete

Post a Comment

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

Golang vs. C#: performance characteristics (simple case study)

Advent of Code - Day 7, 2024: Backtracking and Eval