178. Rank Scores
Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 51.0%
Problem Breakdown
The goal is to assign ranks to scores in descending order based on their values. The input consists of a table Scores containing an ID and a numeric score. We need to output two columns: the original score and its corresponding rank.
Key constraints include handling duplicate scores (ties). If multiple rows have identical scores, they must receive the same rank number. Crucially, for this specific problem variant on LeetCode (#178), we typically expect “dense ranking,” meaning there are no gaps in rank numbers between distinct score values (e.g., if two people tie at Rank 2, the next person gets Rank 3, not Rank 4). We must also handle potential floating-point precision issues implicitly by relying on direct equality checks within sorted data.
Intuition
A naive approach would be to sort all scores in descending order and then iterate through them manually. However, simply sorting doesn’t give us ranks; we need a way to track how many distinct higher values exist before the current row.
In SQL terms, this is exactly what Window Functions are designed for: calculating an aggregate metric over a window of rows defined by ORDER BY. A brute-force implementation in Python would involve nested loops or self-joins to count distinct scores greater than each score, which leads to O(N^2) complexity—too slow.
The key insight is that we can achieve this ranking logic efficiently using the sorting order and a single pass iteration (or SQL’s DENSE_RANK). We only need to increment our rank counter when we encounter a strictly smaller score; if the current score matches the previous one, the rank remains unchanged.
Approach
I will implement this algorithmically in Python since that is requested for the solution block, though it mirrors the logic of SQL window functions:
- Sort the input data by
scoredescending to process highest scores first. - Iterate through the sorted list while maintaining a state variable (
current_rank) and tracking the value of the previous score processed. - If the current row’s score is equal to the previous one, assign the same rank (dense ranking).
- Otherwise, increment the rank counter by 1 for distinct scores.
- Construct the result list with
score, calculatedrank, and preserve original data likeid.
This approach ensures O(N log N) time complexity due to sorting, which is optimal given we must order the data anyway. Space complexity remains linear relative to input size to store results.
Complexity Analysis
- Time: where is the number of rows in
Scores. This is dominated by the initial sort operation required for ranking logic. The subsequent iteration is . - Space: auxiliary space to store the sorted data (Timsort requires O(N)) and the output list containing all results. While sorting algorithms vary, Python’s Timsort uses linear extra memory in worst-case scenarios relative to input size for buffers.
Solution
from typing import List, Dict
def rank_scores(scores: List[Dict]) -> List[Dict]:
"""
Assigns ranks to scores in descending order.
Handles ties by assigning the same dense rank (no gaps).
Args:
scores: A list of dictionaries with keys 'score' and optionally 'id'.
Returns:
List of dicts containing 'score', 'rank', and original 'id'.
"""
# Sort descending to process highest scores first.
sorted_scores = sorted(scores, key=lambda x: x['score'], reverse=True)
result = []
current_rank = 0
prev_score = None
for row in sorted_scores:
score = row['score']
if prev_score is not None and score == prev_score:
# Same rank as previous (Dense Ranking)
pass
else:
# New distinct score, increment rank counter
current_rank += 1
result.append({
'score': score,
'rank': current_rank,
'id': row.get('id') if isinstance(row, dict) and 'id' in row else None
})
prev_score = score
return result
# Example usage matching LeetCode schema structure:
if __name__ == "__main__":
data = [
{"score": 3.5, "id": 1},
{"score": 2.0, "id": 2},
{"score": 3.5, "id": 3} # Tie with first row
]
print(rank_scores(data))
Edge Cases Handled
- Empty Input: The loop simply does not execute; returns an empty list immediately.
- All Scores Identical:
prev_scorematches every iteration, so rank remains 1 for all rows (Dense Rank). - Negative Scores: Sorting logic handles negative numbers correctly in descending order without special handling.
- Floating Point Precision: Direct equality checks (
score == prev_score) are used here assuming standard float behavior; strictly speaking, exact match is expected based on problem constraints where scores usually come from a database schema with defined precision (e.g., DECIMAL).