LeetCode 506: Relative Ranks Solution in Python – A Step-by-Step Guide

What Is LeetCode 506: Relative Ranks?

In LeetCode 506: Relative Ranks, you’re given a list of integer scores, and your task is to return a list of strings representing each score’s rank. The highest score gets "Gold Medal," the second gets "Silver Medal," the third gets "Bronze Medal," and others get their numerical rank (e.g., "4", "5"). For example, with scores [5, 4, 3, 2, 1], the output is ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]. This problem tests your ability to sort and map values, similar to LeetCode 1331: Rank Transform of an Array.

Problem Statement

• Input: List of integers score.
• Output: List of strings—relative ranks with medals for top 3.
• Rules: Higher score = better rank; ties aren’t specified (assume distinct scores).

Constraints

• 1 <= score.length <= 10⁴
• 0 <= score[i] <= 10⁶
• All scores are unique.

Examples

• Input: [5,4,3,2,1]
• Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
• 5 (1st), 4 (2nd), 3 (3rd), etc.
• Input: [10,3,8,9,4]
• Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
• 10 (1st), 9 (2nd), 8 (3rd), 4 (4th), 3 (5th).
• Input: [1]
• Output: ["Gold Medal"]
• Single score gets gold.

Understanding the Problem: Awarding Ranks and Medals

To solve LeetCode 506: Relative Ranks in Python, we need a function that takes a list of scores and returns their ranks as strings, with special labels for the top three. The key is to preserve the original order while assigning ranks based on sorted values. We’ll explore:

• Best Solution (Sorting with Index Mapping): O(n log n) time, O(n) space—fast and intuitive.
• Alternative Solution (Heap): O(n log n) time, O(n) space—different but still efficient.

Let’s dive into the sorting solution with a friendly breakdown!

Best Solution: Sorting with Index Mapping

Why Sorting with Index Mapping Wins

The sorting with index mapping approach is the best for LeetCode 506 because it’s efficient and straightforward. By sorting scores with their indices, we can map each score to its rank in O(n log n) time and O(n) space, then assign medals or numbers. It’s like organizing a leaderboard and handing out awards in one smooth pass!

How It Works

Think of this as a medal ceremony:

• Step 1: Pair Scores with Indices:
• Create a list of (score, index) pairs to track original positions.
• Step 2: Sort in Descending Order:
• Sort by score, highest first, to determine ranks.
• Step 3: Assign Ranks:
• Top 3 get "Gold Medal," "Silver Medal," "Bronze Medal."
• Others get their position (e.g., "4").
• Step 4: Map Back:
• Use original indices to place ranks in the input order.
• Why It Works:
• Sorting gives rank order.
• Indices preserve input sequence.

It’s like sorting the podium and announcing winners!

Step-by-Step Example

Example: [10,3,8,9,4]

• Init:
• pairs = [(10,0), (3,1), (8,2), (9,3), (4,4)].
• result = [""] * 5.
• Step 1: Sort Descending:
• [(10,0), (9,3), (8,2), (4,4), (3,1)].
• Step 2: Assign Ranks:
• Rank 1: (10,0) → "Gold Medal".
• Rank 2: (9,3) → "Silver Medal".
• Rank 3: (8,2) → "Bronze Medal".
• Rank 4: (4,4) → "4".
• Rank 5: (3,1) → "5".
• Step 3: Map to Result:
• result[0] = "Gold Medal".
• result[1] = "5".
• result[2] = "Bronze Medal".
• result[3] = "Silver Medal".
• result[4] = "4".
• Result: ["Gold Medal","5","Bronze Medal","Silver Medal","4"].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        # Step 1: Pair scores with indices
        score_with_index = [(s, i) for i, s in enumerate(score)]

        # Step 2: Sort in descending order
        score_with_index.sort(reverse=True)

        # Step 3: Initialize result array
        n = len(score)
        result = [""] * n

        # Step 4: Assign ranks
        for rank, (s, i) in enumerate(score_with_index):
            if rank == 0:
                result[i] = "Gold Medal"
            elif rank == 1:
                result[i] = "Silver Medal"
            elif rank == 2:
                result[i] = "Bronze Medal"
            else:
                result[i] = str(rank + 1)  # 1-based rank

        return result

• Line 4: Create (score, index) pairs to track positions.
• Line 7: Sort descending by score.
• Lines 10-11: Empty result array sized to input.
• Lines 14-20: Loop through sorted pairs:
• Rank 0 (1st): "Gold Medal".
• Rank 1 (2nd): "Silver Medal".
• Rank 2 (3rd): "Bronze Medal".
• Others: Convert rank (0-based) to 1-based string.
• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(n)—pairs and result.

It’s like a quick medal sorter!

Alternative Solution: Using a Heap

Why an Alternative Approach?

The heap-based solution uses a max-heap to pop scores in descending order, assigning ranks as we go. It’s also O(n log n) time and O(n) space, offering a different perspective using Python’s heapq module. It’s less common but great for heap practice in Python.

How It Works

Picture this as a priority podium:

• Step 1: Build a max-heap of (score, index) pairs.
• Step 2: Pop elements one-by-one.
• Step 3: Assign ranks (medals or numbers) based on order.
• Step 4: Map back to original positions.

It’s like pulling winners off a priority list!

Step-by-Step Example

Example: [5,4,3,2,1]

• Init:
• Heap: [(-5,0), (-4,1), (-3,2), (-2,3), (-1,4)] (negated for max).
• result = [""] * 5.
• Step 1: Pop (-5,0):
• result[0] = "Gold Medal".
• Step 2: Pop (-4,1):
• result[1] = "Silver Medal".
• Step 3: Pop (-3,2):
• result[2] = "Bronze Medal".
• Step 4: Pop (-2,3):
• result[3] = "4".
• Step 5: Pop (-1,4):
• result[4] = "5".
• Result: ["Gold Medal","Silver Medal","Bronze Medal","4","5"].

Code for Heap Approach

Copy codeimport heapq

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        # Step 1: Build max-heap (negate scores)
        heap = [(-s, i) for i, s in enumerate(score)]
        heapq.heapify(heap)

        # Step 2: Initialize result
        n = len(score)
        result = [""] * n

        # Step 3: Assign ranks
        rank = 0
        while heap:
            s, i = heapq.heappop(heap)
            rank += 1
            if rank == 1:
                result[i] = "Gold Medal"
            elif rank == 2:
                result[i] = "Silver Medal"
            elif rank == 3:
                result[i] = "Bronze Medal"
            else:
                result[i] = str(rank)

        return result

• Line 6: Negate scores for max-heap, pair with indices.
• Line 7: Heapify in O(n).
• Lines 10-11: Empty result array.
• Lines 14-22: Pop from heap, assign ranks 1-based.
• Time Complexity: O(n log n)—heap ops.
• Space Complexity: O(n)—heap and result.

It’s a heap-powered ranker!

Comparing the Two Solutions

• Sorting (Best):
• Pros: O(n log n), clear and direct.
• Cons: Sorting syntax.
• Heap (Alternative):
• Pros: O(n log n), heap practice.
• Cons: Slightly trickier with negation.

Sorting wins for simplicity!

Additional Examples and Edge Cases

• [1]: ["Gold Medal"].
• [3,2]: ["Gold Medal","Silver Medal"].
• [10,10]: (Assumes unique, but if not, still works).

Sorting handles them all!

Complexity Recap

• Sorting: Time O(n log n), Space O(n).
• Heap: Time O(n log n), Space O(n).

Both are solid, sorting’s cleaner!

Key Takeaways

• Sorting: Index mapping = win—learn at Python Basics!
• Heaps: Priority fun.
• Ranks: Medals add flair.
• Python: Lists shine!

Final Thoughts: Award Those Medals!

LeetCode 506: Relative Ranks in Python is a delightful ranking challenge. Sorting with index mapping is your fast track, while heaps offer a fun twist. Want more? Try LeetCode 1331: Rank Transform of an Array or LeetCode 1636: Sort Array by Increasing Frequency. Ready to rank? Head to Solve LeetCode 506 on LeetCode and hand out those medals today!