506. Relative Ranks

https://leetcode.com/problems/relative-ranks/

Level: Easy

Solution 1 $\mathcal{O}(N^2)$

def get_str(n: int):
    if n == 1:
        return "Gold Medal"
    elif n == 2:
        return "Silver Medal"
    elif n == 3:
        return "Bronze Medal"
    else:
        return str(n)


class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        """O(N^2)"""
        sorted_score = sorted(score, reverse=True)
        m = {}  # map value to rank
        for idx, x in enumerate(score):
            m[x] = sorted_score.index(x) + 1
        return [get_str(m[x]) for x in score]

Solution 2 $\mathcal{O}(N \log N)$

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        """O(n*logn)"""
        sorted_score = sorted(score, reverse=True) # O(n*logn)
        idx_map = {} # map value to its index in the original list
        for idx, x in enumerate(score): # O(n)
            idx_map[x] = idx

        ret = [None for _ in range(len(score))] # O(n)
        for idx, x in enumerate(sorted_score): # O(n)
            ret[idx_map[x]] = get_str(idx + 1)

        return ret

Solution 3 (Heap) $\mathcal{O}(N\log N)$

Solution 2 maps value to its index in the original list with a loop. Then iterate through sorted list, and fill in result list at original index.

The 2 steps can be combined into one with max heap.

Max heap is a priority queue that always pops the largest element.

During building the heap, we push pairs of (-score, original index) into the heap.

-score is because it's by default a min heap, so we negate the score to make it a max heap.

When popping from the heap, it's sorted by score in descending order.

Since heap sort is also $\mathcal{O}(N\log N)$, the overall time complexity is still $\mathcal{O}(N\log N)$.

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        N = len(score)

        # Create a heap of pairs (score, index)
        heap = []
        for index, score in enumerate(score):
            heapq.heappush(heap, (-score, index))

        # Assign ranks to athletes
        rank = [0] * N
        place = 1
        while heap:
            original_index = heapq.heappop(heap)[1]
            if place == 1:
                rank[original_index] = "Gold Medal"
            elif place == 2:
                rank[original_index] = "Silver Medal"
            elif place == 3:
                rank[original_index] = "Bronze Medal"
            else:
                rank[original_index] = str(place)
            place +=1

        return rank

Solution 4 (Array as Map, No Sort) $\mathcal{O}(N + M)$

I was shocked by the solution 4. It's not perfect but can be much faster.

Solution 2 and 3 have the same philosophy. They require building a map between score and original index, Then fill the rank at the original index. The rank is obtained by sorting the score in descending order.

I though sorting is inevitable, and the optimal time complexity is $\mathcal{O}(N\log N)$.

This solution trades space for time. It uses an array to map score to index. The array is indexed by score. The value is the original index.

Take example [10, 3, 8, 9, 4]

Step 1: Build the map

Although there are 5 elements in the scores list, the range of scores is [3, 10], and could potentially be $[0, \infty]$.

Need to find the max score to determine the size of the array. $\mathcal{O}(N)$. So the array should be of size 11.

For each score $s$, the original index is $i$. The array is updated as score_to_index[s] = i + 1.

index	0	1	2	3	4	5	6	7	8	9	10
original index + 1	0	0	0	2	5	0	0	0	3	4	1

Step 2: Assign ranks

Iterating the map array from right to left, this result in the descending order of scores.

If the score is not 0, then the original index is obtained by score_to_index[s] - 1.

The rank/place and be tracked by a counter, starting from 1. Once a new score is found, the place is incremented. Then fill the result list with rank and original index from score_to_index.

index	0	1	2	3	4
rank	Gold Medal	5	Bronze Medal	Silver Medal	4

Let maximum value be $M$, the score_to_index array has size $M + 1$ [0 - M].

The time complexity is $\mathcal{O}(N + M)$, where $M$ is the maximum score.

class Solution:
    def find_max(self, score):
        max_score = 0
        for s in score:
            if s > max_score :
                max_score = s
        return max_score

    def findRelativeRanks(self, score):
        N = len(score)

        # Add the original index of each score to the array
        # Where the score is the key
        M = self.find_max(score)
        score_to_index = [0] * (M + 1)
        for i in range(N):
            score_to_index[score[i]] = i + 1

        MEDALS = ["Gold Medal", "Silver Medal", "Bronze Medal"]

        # Assign ranks to athletes
        rank = [None] * N
        place = 1
        for i in range(M, -1, -1):
            if score_to_index[i] != 0:
                original_index = score_to_index[i] - 1
                if place < 4:
                    rank[original_index] = MEDALS[place - 1]
                else:
                    rank[original_index] = str(place)
                place += 1
        return rank