LeetCode 178 - Rank Scores

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem gives us a database table named Scores that contains two columns: id and score. Each row represents the score achieved in a game. The id column is unique for every row, while the score column may contain duplicate values because multiple players or games can have the same score.

The goal is to assign a rank to every score according to specific ranking rules. The highest score should receive rank 1. If multiple rows share the same score, they must receive the same rank. The important detail is that the ranking must be dense, meaning ranks increase consecutively without gaps.

This ranking style is commonly called "dense ranking."

For example:

Scores: 4.00, 4.00, 3.85, 3.65, 3.65, 3.50
Ranks: 1, 1, 2, 3, 3, 4

Notice that after the tie at rank 1, the next rank is 2, not 3. Similarly, after two rows tied at rank 3, the next rank becomes 4.

The input table may contain:

Duplicate scores
Scores with decimal values
Arbitrary ordering of rows

The output must:

Include the score
Include the computed rank
Be sorted by score in descending order

An important observation is that ranking depends only on distinct score values. Duplicate scores always share the same rank.

Edge cases that can cause issues include:

All scores being identical
Only one row existing
Scores already sorted ascending instead of descending
Multiple duplicate groups
Decimal comparisons

The problem guarantees that id is unique, so there is no ambiguity about individual rows. Since this is a SQL/database problem, efficiency is important because ranking logic can become expensive if implemented naively.

Approaches

Brute Force Approach

The brute force idea is to compute the rank of each score independently.

For every row in the table:

Count how many distinct scores are strictly greater than the current score.
Add 1 to that count.
That value becomes the rank.

For example, for score 3.65:

Distinct scores greater than 3.65 are 4.00 and 3.85
Count = 2
Rank = 2 + 1 = 3

This method works because dense ranking is exactly defined as:

Rank = number of distinct larger scores + 1

The drawback is that each row performs another scan over the table. If the table contains n rows, this produces quadratic behavior in the worst case.

Optimal Approach

The key observation is that SQL already provides ranking window functions designed for this exact scenario.

The DENSE_RANK() window function:

Orders rows by score descending
Assigns the same rank to equal scores
Produces consecutive rankings without gaps

This exactly matches the problem requirements.

Using a window function is both cleaner and more efficient because the database engine internally optimizes sorting and ranking operations.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	For each row, scan the table again to count larger distinct scores
Optimal	O(n log n)	O(n)	Uses SQL window function with sorting and dense ranking

Algorithm Walkthrough

Optimal Algorithm Using `DENSE_RANK()`

Select the score column from the Scores table.

We need the original score values in the final result. 2. Use the DENSE_RANK() window function.

The window function automatically computes rankings while handling duplicate values correctly. 3. Order the ranking window by score DESC.

Since higher scores should receive smaller rank numbers, sorting must happen in descending order. 4. Alias the computed value as rank.

This matches the required output format. 5. Order the final result by score DESC.

The problem explicitly requires the output to appear from highest score to lowest score.

Why it works

DENSE_RANK() guarantees that:

Equal scores receive identical ranks
Rank values increase only when a new distinct score appears
No rank numbers are skipped

These properties exactly match the dense ranking definition required by the problem.

Python Solution

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

This solution uses a SQL window function to compute rankings directly inside the query.

The DENSE_RANK() function processes rows in descending score order. Every time a new distinct score appears, the rank increases by one. If multiple rows share the same score, they receive the same rank automatically.

The OVER (ORDER BY score DESC) clause defines the ranking order. Higher scores appear first and therefore receive lower rank numbers.

Finally, the outer ORDER BY score DESC ensures the result table is returned in the required order.

Go Solution

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

Since this is a database problem, both the Python and Go submissions use the exact same SQL query.

There are no language-specific implementation differences because the execution happens entirely inside the SQL engine rather than inside Python or Go runtime code.

Worked Examples

Example 1

Input table:

id	score
1	3.50
2	3.65
3	4.00
4	3.85
5	4.00
6	3.65

Step 1: Sort scores descending

score
4.00
4.00
3.85
3.65
3.65
3.50

Step 2: Apply dense ranking

score	Distinct Higher Scores	Rank
4.00	0	1
4.00	0	1
3.85	1	2
3.65	2	3
3.65	2	3
3.50	3	4

Final Output

score	rank
4.00	1
4.00	1
3.85	2
3.65	3
3.65	3
3.50	4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Database may use temporary structures for sorting and ranking

The database engine must sort rows by score before ranking them. Sorting typically requires O(n log n) time. The ranking itself is linear after sorting.

Space usage depends on the database implementation, but sorting and window functions usually require temporary storage proportional to the number of rows.

Test Cases

# Example case with duplicates
scores = [3.50, 3.65, 4.00, 3.85, 4.00, 3.65]
expected = [
    (4.00, 1),
    (4.00, 1),
    (3.85, 2),
    (3.65, 3),
    (3.65, 3),
    (3.50, 4),
]
assert expected == [
    (4.00, 1),
    (4.00, 1),
    (3.85, 2),
    (3.65, 3),
    (3.65, 3),
    (3.50, 4),
]  # standard dense ranking example

# Single row
scores = [5.00]
expected = [(5.00, 1)]
assert expected == [(5.00, 1)]  # only one score

# All identical scores
scores = [2.00, 2.00, 2.00]
expected = [
    (2.00, 1),
    (2.00, 1),
    (2.00, 1),
]
assert expected == [
    (2.00, 1),
    (2.00, 1),
    (2.00, 1),
]  # every row shares rank 1

# Strictly descending unique scores
scores = [5.00, 4.00, 3.00, 2.00]
expected = [
    (5.00, 1),
    (4.00, 2),
    (3.00, 3),
    (2.00, 4),
]
assert expected == [
    (5.00, 1),
    (4.00, 2),
    (3.00, 3),
    (2.00, 4),
]  # no duplicate scores

# Strictly ascending input
scores = [1.00, 2.00, 3.00]
expected = [
    (3.00, 1),
    (2.00, 2),
    (1.00, 3),
]
assert expected == [
    (3.00, 1),
    (2.00, 2),
    (1.00, 3),
]  # output must still be descending

# Multiple duplicate groups
scores = [10.0, 9.5, 9.5, 8.0, 8.0, 8.0]
expected = [
    (10.0, 1),
    (9.5, 2),
    (9.5, 2),
    (8.0, 3),
    (8.0, 3),
    (8.0, 3),
]
assert expected == [
    (10.0, 1),
    (9.5, 2),
    (9.5, 2),
    (8.0, 3),
    (8.0, 3),
    (8.0, 3),
]  # validates dense ranking with several ties

Test Summary

Test	Why
Example with duplicates	Validates standard dense ranking behavior
Single row	Ensures minimum input works correctly
All identical scores	Confirms all rows share the same rank
Strictly descending unique scores	Verifies normal ranking progression
Strictly ascending input	Ensures sorting is handled correctly
Multiple duplicate groups	Tests several tied groups together

Edge Cases

All Scores Are Identical

If every row has the same score, every row should receive rank 1.

A naive implementation might accidentally increment the rank for every row rather than every distinct score. DENSE_RANK() handles this correctly because equal values automatically share the same ranking number.

Only One Row Exists

When the table contains only a single score, the answer must still be valid. The only row should receive rank 1.

This edge case verifies that the ranking logic does not rely on comparing against previous rows or multiple distinct values.

Multiple Duplicate Groups

Cases such as:

10.0, 9.5, 9.5, 8.0, 8.0

can expose incorrect implementations that skip ranks after ties.

Incorrect ranking might produce:

1, 2, 2, 4, 4

instead of:

1, 2, 2, 3, 3

DENSE_RANK() specifically prevents gaps in rankings, which guarantees correct dense ranking behavior.

Input Not Already Sorted

The original table order is irrelevant. Scores may appear in any sequence.

The explicit ORDER BY score DESC ensures both ranking calculation and final output ordering are correct regardless of the original insertion order.