Rank Scores - Solution & Explanation
Problem Statement
Table: Scores
+-------------+---------+ | Column Name | Type | +-------------+---------+ | id | int | | score | decimal | +-------------+---------+ id is the primary key (column with unique values) for this table. Each row of this table contains the score of a game. Score is a floating point value with two decimal places.
Write a solution to find the rank of the scores. The ranking should be calculated according to the following rules:
- The scores should be ranked from the highest to the lowest.
- If there is a tie between two scores, both should have the same ranking.
- After a tie, the next ranking number should be the next consecutive integer value. In other words, there should be no holes between ranks.
Return the result table ordered by score in descending order.
The result format is in the following example.
Example 1:
Input: Scores table: +----+-------+ | id | score | +----+-------+ | 1 | 3.50 | | 2 | 3.65 | | 3 | 4.00 | | 4 | 3.85 | | 5 | 4.00 | | 6 | 3.65 | +----+-------+ Output: +-------+------+ | score | rank | +-------+------+ | 4.00 | 1 | | 4.00 | 1 | | 3.85 | 2 | | 3.65 | 3 | | 3.65 | 3 | | 3.50 | 4 | +-------+------+
Approach Overview
Problem Overview: You are given a table of scores where multiple players may share the same score. The task is to assign a rank to each score in descending order. Players with identical scores receive the same rank, and the next rank should not skip numbers (dense ranking).
Approach 1: Sorting and Rank Assignment (O(n log n) time, O(n) space)
The straightforward strategy is to sort scores in descending order and assign ranks as you iterate through the sorted list. When the current score is the same as the previous one, reuse the same rank. When the score changes, increment the rank counter. This approach relies on a sorting step followed by a single pass to assign ranks. The key insight is tracking the previous score and current rank while iterating. Sorting dominates the runtime, giving O(n log n) time and O(n) auxiliary space if a copy of the scores is created. This method is reliable and easy to implement using standard sorting utilities.
Approach 2: Bucket Sort with Counting (O(n + k) time, O(k) space)
If the score range is limited, you can avoid full sorting by using a bucket or counting array. First scan the dataset to determine the maximum score. Create a frequency array where each index represents a score value. Populate counts for each score, then traverse the buckets from highest to lowest to assign ranks. Each distinct score encountered increments the rank counter, and all entries in that bucket share the same rank. This converts the ranking problem into a frequency counting task using techniques similar to counting sort. The complexity becomes O(n + k), where k is the score range, making it efficient when k is relatively small compared to n.
Recommended for interviews: Sorting and rank assignment is the most common expectation. It demonstrates clear reasoning and works for any dataset without assumptions about score range. Bucket-based counting can be faster but depends on constraints about score values. Interviewers typically accept the sorting approach first, then appreciate discussion of counting optimizations if the range is bounded. The underlying concept also appears frequently in database ranking problems where dense ranking is required.
Approach 1: Approach 1: Sorting and Rank Assignment
This approach involves sorting the scores in descending order, then iteratively assigning ranks to each score while handling ties appropriately. This can be efficiently achieved using a sorting algorithm followed by a traversal to assign ranks. By maintaining an index while sorting, we can assign ranks directly to the original scores.
The C implementation uses a structure to store each score with its ID. The scores are sorted in descending order using `qsort()` and a custom comparator. During sorting, ties are managed by assigning the same rank, replicating an Excel-like RANK function behavior. The solution uses a single scan to determine ranks after sorting.
Complexity
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(1), only a fixed amount of additional memory is used for sorting.
Approach 2: Approach 2: Bucket Sort with Counting
This approach uses a bucket sort strategy, particularly efficient when scores have a limited range of decimal places. This reduces the complexity substantially in scenarios where HTTP (High Throughput Processing) is required. Counting occurrences of each score allows direct assignment of ranks in descending order of scores efficiently.
The C bucket sort implementation converts each score based on its proximity to MIN_SCORE using a defined bucket size. Each score increments its corresponding bucket to count occurrences. The ranks are assigned by iteratively checking non-empty buckets from highest to lowest.
Complexity
Time Complexity: O(n + k), where n is the number of scores, and k is the number of buckets (constant in this case).
Space Complexity: O(k), which is fixed and depends on BUCKET_COUNT.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Rank Assignment | Time Complexity: O(n log n) due to the sorting operation. |
| Approach 2: Bucket Sort with Counting | Time Complexity: O(n + k), where n is the number of scores, and k is the number of buckets (constant in this case). |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Rank Assignment | O(n log n) | O(n) | General case where score range is unknown or large |
| Bucket Sort with Counting | O(n + k) | O(k) | When score values fall within a limited numeric range |
Video Solution
LeetCode 178: Rank Scores [SQL] • Frederik Müller • 17,570 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Rank Scores easy or hard?
Rank Scores Python/Java solution
How to solve Rank Scores in O(n)?
What is the best approach for Rank Scores?
Is Rank Scores asked at Google/Amazon/Meta?
What data structure is used in Rank Scores?
What is the time complexity of Rank Scores?
Ready to solve this problem?
Practice Rank Scores with our built-in code editor and test cases.
Practice on FleetCode