LeetCode 178: Rank Scores (Dense Ranking with SQL Window Function)

Today we solve LeetCode 178 - Rank Scores.

Source: https://leetcode.com/problems/rank-scores/

English

Problem Summary

Given table Scores(id, score), return every score and its rank. Equal scores share the same rank, and the next distinct score gets the next consecutive rank (dense ranking).

Key Insight

This is exactly DENSE_RANK() behavior: sort scores descending, then assign equal values the same rank without gaps.

SQL Strategy

- Sort by score DESC.
- Use DENSE_RANK() OVER (ORDER BY score DESC).
- Output columns as score and rank.

Complexity Analysis

Main cost comes from sorting: roughly O(n log n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

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

std::string sql = R"SQL(
SELECT
  score,
  DENSE_RANK() OVER (ORDER BY score DESC) AS `rank`
FROM Scores
ORDER BY score DESC;
)SQL";

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

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

中文

题目概述

给定 Scores(id, score) 表，返回每个分数及其排名。相同分数并列，同一并列后面的下一个不同分数排名只加 1（稠密排名）。

核心思路

题意就是 SQL 的 DENSE_RANK()：按分数降序排序，分数相同给同一名次，且名次不跳号。

SQL 解法

- 按 score DESC 排序。
- 使用 DENSE_RANK() OVER (ORDER BY score DESC) 生成排名。
- 输出字段为 score 与 rank。

复杂度分析

主要开销在排序，约为 O(n log n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

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

std::string sql = R"SQL(
SELECT
  score,
  DENSE_RANK() OVER (ORDER BY score DESC) AS `rank`
FROM Scores
ORDER BY score DESC;
)SQL";

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

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