# 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:

```sql
score, rank
```

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

```sql
`rank`
```

## Examples

Example:

```text
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:

```text
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:

```text
+-------+------+
| 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:

```text
4.00
```

Count is `1`, so rank is `1`.

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

```text
4.00, 3.85
```

Count is `2`, so rank is `2`.

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

```text
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:

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

## Correctness

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

Here, the ordering is:

```sql
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

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

## Code Explanation

This selects the original score:

```sql
score
```

Then this computes the dense rank:

```sql
DENSE_RANK() OVER (ORDER BY score DESC)
```

The `OVER` clause defines how the ranking is computed.

The ordering:

```sql
ORDER BY score DESC
```

places higher scores before lower scores.

Finally, this names the computed column:

```sql
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.

```sql
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:

```text
4.00, 3.85, 3.65
```

So the rank is `3`.

## Testing

Test case 1:

```sql
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:

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

Test case 2:

```sql
DELETE FROM Scores;

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

Expected:

```text
+-------+------+
| score | rank |
+-------+------+
| 5.00  | 1    |
+-------+------+
```

Test case 3:

```sql
DELETE FROM Scores;

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

Expected:

```text
+-------+------+
| score | rank |
+-------+------+
| 2.00  | 1    |
| 2.00  | 1    |
| 2.00  | 1    |
+-------+------+
```

Test case 4:

```sql
DELETE FROM Scores;

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

Expected:

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