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:
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 | +-------+------+
Problem Overview: You are given a table of scores. The task is to assign a rank to each score in descending order. If multiple rows share the same score, they receive the same rank. The next distinct score should receive the next consecutive rank without gaps (dense ranking).
Approach 1: Sorting and Rank Assignment (O(n log n) time, O(n) space)
The straightforward method sorts all scores in descending order and assigns ranks while iterating through the sorted list. After sorting, you maintain a variable for the current rank and update it only when you encounter a new score value. If the current score equals the previous one, the rank stays the same. Otherwise, increment the rank. This technique relies on classic sorting followed by a single linear pass.
This approach works well because sorting groups identical scores together, making rank assignment trivial. The implementation simply tracks the previous score and current rank during iteration. Time complexity is O(n log n) due to sorting, while the rank assignment scan runs in O(n). Space complexity is typically O(n) if a new structure or sorted copy is used.
In SQL-based environments, this logic is commonly implemented with DENSE_RANK() OVER (ORDER BY score DESC). That window function internally performs ordering and rank generation, which maps directly to the same conceptual algorithm. This problem frequently appears in database query interviews.
Approach 2: Bucket Sort with Counting (O(n + k) time, O(k) space)
If the score range is limited, you can avoid comparison-based sorting by using a counting or bucket strategy. First, scan the input and count occurrences of each score using a frequency structure such as an array or hash map. Then iterate through the score range in descending order. Each time you encounter a score that exists in the frequency map, assign the next rank and apply it to all rows with that score.
This technique behaves like counting sort. Because it skips comparison sorting, the complexity becomes O(n + k), where k is the score range. Space complexity is O(k) for the bucket structure. The approach is efficient when the score range is small relative to the number of rows.
Recommended for interviews: The sorting approach is the safest explanation. It demonstrates understanding of ordering and rank handling, which matches how SQL window functions operate internally. Mentioning the bucket/counting optimization shows deeper algorithm knowledge, but interviewers typically expect the sorting or DENSE_RANK() solution first.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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 | 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). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Rank Assignment | O(n log n) | O(n) | General case when scores are arbitrary and you rely on sorting or SQL window functions |
| Bucket Sort with Counting | O(n + k) | O(k) | When score values fall within a limited range and counting is more efficient than sorting |
Minimum Difference Between Highest and Lowest of K Scores - Leetcode Weekly Contest - 1984 Python • NeetCode • 19,321 views views
Watch 9 more video solutions →Practice Rank Scores with our built-in code editor and test cases.
Practice on FleetCode