LeetCode 178: Rank Scores

Problem Restatement

We are given a table named Scores.

Column	Type
id	int
score	decimal

Each row stores the score of a game.

We need to rank all scores from highest to lowest.

The ranking rules are:

Rule	Meaning
Higher score gets smaller rank	The highest score has rank `1`
Equal scores share the same rank	Two `4.00` scores both get rank `1`
No rank gaps	After rank `1`, the next different score gets rank `2`

This ranking style is called dense ranking.

The result must be ordered by score in descending order. The official statement says to rank scores highest to lowest, ties share the same ranking, and after a tie the next rank is the next consecutive integer.

Input and Output

Item	Meaning
Input	Table `Scores(id, score)`
Output	Columns `score` and `rank`
Ordering	Result ordered by `score DESC`
Ranking rule	Dense rank

Expected output columns:

score, rank

Because rank can be a reserved word in SQL, we usually wrap it in backticks in MySQL:

`rank`

Examples

Example:

Scores
+----+-------+
| id | score |
+----+-------+
| 1  | 3.50  |
| 2  | 3.65  |
| 3  | 4.00  |
| 4  | 3.85  |
| 5  | 4.00  |
| 6  | 3.65  |
+----+-------+

Sort scores from highest to lowest:

4.00
4.00
3.85
3.65
3.65
3.50

Now assign dense ranks:

Score	Rank	Reason
4.00	1	Highest score
4.00	1	Tie with previous score
3.85	2	Next distinct score
3.65	3	Next distinct score
3.65	3	Tie with previous score
3.50	4	Next distinct score

Output:

+-------+------+
| score | rank |
+-------+------+
| 4.00  | 1    |
| 4.00  | 1    |
| 3.85  | 2    |
| 3.65  | 3    |
| 3.65  | 3    |
| 3.50  | 4    |
+-------+------+

First Thought: Count Higher Distinct Scores

For each score, we can compute its rank by counting how many distinct scores are greater than or equal to it.

For score 4.00, distinct scores greater than or equal to it:

4.00

Count is 1, so rank is 1.

For score 3.85, distinct scores greater than or equal to it:

4.00, 3.85

Count is 2, so rank is 2.

For score 3.65, distinct scores greater than or equal to it:

4.00, 3.85, 3.65

Count is 3, so rank is 3.

This logic works, but modern SQL gives us a cleaner built-in tool.

Key Insight

This problem asks exactly for DENSE_RANK().

DENSE_RANK() assigns ranks after sorting rows.

It has two important properties:

Function	Ties	Rank gaps
`ROW_NUMBER()`	Different numbers	No gaps
`RANK()`	Same number	Has gaps
`DENSE_RANK()`	Same number	No gaps

We need ties to share the same rank and we need no gaps, so DENSE_RANK() is the right function.

Algorithm

Use a window function:

Read all rows from Scores.
Sort rows by score DESC inside the window.
Apply DENSE_RANK().
Return score and the computed rank.

Correctness

DENSE_RANK() ranks rows according to the order specified inside OVER.

Here, the ordering is:

ORDER BY score DESC

So the highest score receives rank 1.

When two rows have the same score, they have the same ordering value. DENSE_RANK() assigns them the same rank.

When the next lower distinct score appears, DENSE_RANK() increases the rank by exactly 1.

Therefore, the ranks follow all problem rules: highest to lowest, ties share a rank, and no rank numbers are skipped.

Complexity

Metric	Value	Why
Time	`O(n log n)`	The database must order rows by score
Space	`O(n)`	The database may materialize sorted or ranked rows

With an index on score, the database may reduce sorting cost, but the logical operation is still based on ordering the rows.

Implementation

SELECT
    score,
    DENSE_RANK() OVER (ORDER BY score DESC) AS `rank`
FROM Scores;

Code Explanation

This selects the original score:

score

Then this computes the dense rank:

DENSE_RANK() OVER (ORDER BY score DESC)

The OVER clause defines how the ranking is computed.

The ordering:

ORDER BY score DESC

places higher scores before lower scores.

Finally, this names the computed column:

AS `rank`

Backticks are useful in MySQL because rank is also the name of a ranking function.

Alternative Implementation

For older MySQL versions without window functions, we can use a correlated subquery.

SELECT
    s1.score,
    (
        SELECT COUNT(DISTINCT s2.score)
        FROM Scores s2
        WHERE s2.score >= s1.score
    ) AS `rank`
FROM Scores s1
ORDER BY s1.score DESC;

For each row s1, the subquery counts distinct scores greater than or equal to s1.score.

That count is the dense rank.

For example, if s1.score = 3.65, the distinct scores greater than or equal to it are:

4.00, 3.85, 3.65

So the rank is 3.

Testing

Test case 1:

CREATE TABLE Scores (
    id INT PRIMARY KEY,
    score DECIMAL(3,2)
);

INSERT INTO Scores (id, score) VALUES
(1, 3.50),
(2, 3.65),
(3, 4.00),
(4, 3.85),
(5, 4.00),
(6, 3.65);

SELECT
    score,
    DENSE_RANK() OVER (ORDER BY score DESC) AS `rank`
FROM Scores;

Expected:

+-------+------+
| score | rank |
+-------+------+
| 4.00  | 1    |
| 4.00  | 1    |
| 3.85  | 2    |
| 3.65  | 3    |
| 3.65  | 3    |
| 3.50  | 4    |
+-------+------+

Test case 2:

DELETE FROM Scores;

INSERT INTO Scores (id, score) VALUES
(1, 5.00);

Expected:

+-------+------+
| score | rank |
+-------+------+
| 5.00  | 1    |
+-------+------+

Test case 3:

DELETE FROM Scores;

INSERT INTO Scores (id, score) VALUES
(1, 2.00),
(2, 2.00),
(3, 2.00);

Expected:

+-------+------+
| score | rank |
+-------+------+
| 2.00  | 1    |
| 2.00  | 1    |
| 2.00  | 1    |
+-------+------+

Test case 4:

DELETE FROM Scores;

INSERT INTO Scores (id, score) VALUES
(1, 1.00),
(2, 3.00),
(3, 2.00);

Expected:

+-------+------+
| score | rank |
+-------+------+
| 3.00  | 1    |
| 2.00  | 2    |
| 1.00  | 3    |
+-------+------+