Watch 10 video solutions for Rank Scores, a medium level problem involving Database. This walkthrough by NeetCode has 19,321 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 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 | 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 |
