How do you solve Relative Ranks on LeetCode?

Relative Ranks (LeetCode #506) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Sorting is a powerful tool for ranking problems, as it allows us to easily determine the order of elements.

What is the time complexity of Relative Ranks?

The optimal solution for Relative Ranks runs in O(n log n) time and uses O(n) space. The sorting step dominates the time complexity, as sorting takes O(n log n), and we use O(n) space to store the indexed scores.

What is the brute force solution for Relative Ranks?

The brute force approach for Relative Ranks is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we can determine the rank of each athlete by comparing their scores with every other athlete's score. This means for each athlete, we count how many athletes have a higher score than them to determine their rank. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Relative Ranks?

Relative Ranks uses the following concepts: Array, Sorting, Heap (Priority Queue). The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Relative Ranks?

Always clarify the problem requirements and constraints before jumping to a solution. Think about edge cases, such as the minimum number of athletes. Practice explaining your thought process as you code, as communication is key in interviews.

What are common mistakes when solving Relative Ranks?

Forgetting to handle the special cases for ranks (Gold, Silver, Bronze) correctly. Not considering the need to maintain the original indices when sorting.

#506

Relative Ranks

Easy

ArraySortingHeap (Priority Queue)Hash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

In the optimal approach, we can sort the scores while keeping track of their original indices. This allows us to assign ranks based on their sorted positions efficiently.

⚙️

Algorithm

3 steps

1Step 1: Create a list of tuples containing each athlete's score and their original index.
2Step 2: Sort this list based on scores in descending order.
3Step 3: Create an output array and assign ranks based on the sorted order: 'Gold Medal', 'Silver Medal', 'Bronze Medal', and the respective position for others.

solution.py20 lines

1# Full working Python code
2score = [5, 4, 3, 2, 1]
3
4def findRelativeRanks(score):
5    n = len(score)
6    indexed_scores = [(s, i) for i, s in enumerate(score)]
7    indexed_scores.sort(reverse=True, key=lambda x: x[0])
8    ranks = [''] * n
9    for rank, (s, i) in enumerate(indexed_scores):
10        if rank == 0:
11            ranks[i] = 'Gold Medal'
12        elif rank == 1:
13            ranks[i] = 'Silver Medal'
14        elif rank == 2:
15            ranks[i] = 'Bronze Medal'
16        else:
17            ranks[i] = str(rank + 1)
18    return ranks
19
20print(findRelativeRanks(score))

ℹ

Complexity note: The sorting step dominates the time complexity, as sorting takes O(n log n), and we use O(n) space to store the indexed scores.

1Sorting is a powerful tool for ranking problems, as it allows us to easily determine the order of elements.
2Using additional data structures (like tuples or pairs) can help maintain original indices while sorting.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.