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 | +-------+------+
The #178 Rank Scores problem asks you to assign ranks to scores stored in a database table. The key requirement is that identical scores must receive the same rank, and the next rank should follow a dense ranking pattern (no gaps between ranks). For example, if two scores share rank 1, the next unique score should receive rank 2.
A common approach is to use SQL window functions, particularly DENSE_RANK(), which naturally handles duplicate values and produces continuous ranking. By ordering the scores in descending order inside the window function, you can compute the required ranking directly.
If window functions are unavailable, another strategy is a correlated subquery. This approach counts the number of distinct scores greater than the current score and derives the rank from that count. While conceptually straightforward, it may be less efficient on large datasets.
Overall, the window function approach is typically preferred for clarity and performance, relying mainly on sorting operations within the database engine.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Window Function (DENSE_RANK) | O(n log n) | O(n) |
| Correlated Subquery | O(n^2) | O(1) |
NeetCode
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.
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.
1const scores = [
2 { id: 1, score: 3.50 },
3 { id: 2, score: 3.65 }
JavaScript takes advantage of the sort function on arrays, providing a compare function to sort scores in descending order. Ranks are then assigned by iterating over the sorted array, with efficient handling of ties using simple conditionals.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The most efficient approach is using the SQL window function DENSE_RANK(). It ranks rows based on ordered values while ensuring that identical scores share the same rank without leaving gaps between ranks.
Yes, it can be solved using a correlated subquery that counts distinct scores greater than the current score. This method works in older SQL versions but is generally slower compared to window functions.
Yes, ranking queries like Rank Scores are common in SQL interviews. They test understanding of ordering, window functions, and how to handle duplicates when assigning ranks.
Window functions, especially DENSE_RANK(), are the best feature for solving this problem. They allow ranking rows within a result set while preserving order and handling duplicates efficiently.
In JavaScript, a Map structure is used to count instances of scores in buckets calculated by integer conversion. Sorted in descending order, each bucket's contents are examined, and ranks are adapted accordingly. This allows fast iteration and logging for real-time HTTP applications.