178. Rank Scores - Solution & Explanation

The problem

Table: Scores

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| score       | decimal |
+-------------+---------+
id is the primary key (column with unique values) for this table.
Each row of this table contains the score of a game. Score is a floating point value with two decimal places.

Write a solution to find the rank of the scores. The ranking should be calculated according to the following rules:

The scores should be ranked from the highest to the lowest.
If there is a tie between two scores, both should have the same ranking.
After a tie, the next ranking number should be the next consecutive integer value. In other words, there should be no holes between ranks.

Return the result table ordered by score in descending order.

The result format is in the following example.

Example 1:

Input: 
Scores table:
+----+-------+
| id | score |
+----+-------+
| 1  | 3.50  |
| 2  | 3.65  |
| 3  | 4.00  |
| 4  | 3.85  |
| 5  | 4.00  |
| 6  | 3.65  |
+----+-------+
Output: 
+-------+------+
| score | rank |
+-------+------+
| 4.00  | 1    |
| 4.00  | 1    |
| 3.85  | 2    |
| 3.65  | 3    |
| 3.65  | 3    |
| 3.50  | 4    |
+-------+------+

Approach overview

Problem Overview: You are given a table of scores where multiple players may share the same score. The task is to assign a rank to each score in descending order. Players with identical scores receive the same rank, and the next rank should not skip numbers (dense ranking).

Approach 1: Sorting and Rank Assignment (O(n log n) time, O(n) space)

The straightforward strategy is to sort scores in descending order and assign ranks as you iterate through the sorted list. When the current score is the same as the previous one, reuse the same rank. When the score changes, increment the rank counter. This approach relies on a sorting step followed by a single pass to assign ranks. The key insight is tracking the previous score and current rank while iterating. Sorting dominates the runtime, giving O(n log n) time and O(n) auxiliary space if a copy of the scores is created. This method is reliable and easy to implement using standard sorting utilities.

Approach 2: Bucket Sort with Counting (O(n + k) time, O(k) space)

If the score range is limited, you can avoid full sorting by using a bucket or counting array. First scan the dataset to determine the maximum score. Create a frequency array where each index represents a score value. Populate counts for each score, then traverse the buckets from highest to lowest to assign ranks. Each distinct score encountered increments the rank counter, and all entries in that bucket share the same rank. This converts the ranking problem into a frequency counting task using techniques similar to counting sort. The complexity becomes O(n + k), where k is the score range, making it efficient when k is relatively small compared to n.

Recommended for interviews: Sorting and rank assignment is the most common expectation. It demonstrates clear reasoning and works for any dataset without assumptions about score range. Bucket-based counting can be faster but depends on constraints about score values. Interviewers typically accept the sorting approach first, then appreciate discussion of counting optimizations if the range is bounded. The underlying concept also appears frequently in database ranking problems where dense ranking is required.

Approach 1: Approach 1: Sorting and Rank Assignment

This approach involves sorting the scores in descending order, then iteratively assigning ranks to each score while handling ties appropriately. This can be efficiently achieved using a sorting algorithm followed by a traversal to assign ranks. By maintaining an index while sorting, we can assign ranks directly to the original scores.

Python

class ScoreEntry:
    def __init__(self, id, score):
        self.id = id
        self.score = score

scores = [
    ScoreEntry(1, 3.50),
    ScoreEntry(2, 3.65),
    ScoreEntry(3, 4.00),
    ScoreEntry(4, 3.85),
    ScoreEntry(5, 4.00),
    ScoreEntry(6, 3.65)
]

scores.sort(key=lambda x: x.score, reverse=True)

rank = 1
for i in range(len(scores)):
    if i == 0 or scores[i].score != scores[i - 1].score:
        rank = i + 1
    print(f"Score: {scores[i].score}, Rank: {rank}")

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class ScoreEntry {
    int id;
    double score;
    ScoreEntry(int id, double score) {
        this.id = id;
        this.score = score;
    }
}

public class RankScores {
    public static void assignRanks(ArrayList<ScoreEntry> scores) {
        Collections.sort(scores, new Comparator<ScoreEntry>() {
            public int compare(ScoreEntry a, ScoreEntry b) {
                return Double.compare(b.score, a.score);
            }
        });
        int rank = 1;
        for (int i = 0; i < scores.size(); i++) {
            if (i == 0 || scores.get(i).score != scores.get(i - 1).score) {
                rank = i + 1;
            }
            System.out.println("Score: " + scores.get(i).score + ", Rank: " + rank);
        }
    }
    public static void main(String[] args) {
        ArrayList<ScoreEntry> scores = new ArrayList<>();
        scores.add(new ScoreEntry(1, 3.50));
        scores.add(new ScoreEntry(2, 3.65));
        scores.add(new ScoreEntry(3, 4.00));
        scores.add(new ScoreEntry(4, 3.85));
        scores.add(new ScoreEntry(5, 4.00));
        scores.add(new ScoreEntry(6, 3.65));

        assignRanks(scores);
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

struct ScoreEntry {
    int id;
    double score;
};

bool compare(ScoreEntry a, ScoreEntry b) {
    return a.score > b.score;
}

void assignRanks(std::vector<ScoreEntry>& entries) {
    std::sort(entries.begin(), entries.end(), compare);
    int rank = 1;
    for (size_t i = 0; i < entries.size(); ++i) {
        if (i == 0 || entries[i].score != entries[i - 1].score) {
            rank = i + 1;
        }
        std::cout << "Score: " << entries[i].score << ", Rank: " << rank << std::endl;
    }
}

int main() {
    std::vector<ScoreEntry> scores = {
        {1, 3.50}, {2, 3.65}, {3, 4.00}, {4, 3.85}, {5, 4.00}, {6, 3.65}
    };
    assignRanks(scores);
    return 0;
}

JavaScript

const scores = [
  { id: 1, score: 3.50 },
  { id: 2, score: 3.65 },
  { id: 3, score: 4.00 },
  { id: 4, score: 3.85 },
  { id: 5, score: 4.00 },
  { id: 6, score: 3.65 }
];

scores.sort((a, b) => b.score - a.score);

let rank = 1;
for (let i = 0; i < scores.length; i++) {
  if (i === 0 || scores[i].score !== scores[i - 1].score) {
    rank = i + 1;
  }
  console.log(`Score: ${scores[i].score.toFixed(2)}, Rank: ${rank}`);
}

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int id;
    double score;
} ScoreEntry;

int compare(const void *a, const void *b) {
    ScoreEntry *entryA = (ScoreEntry *)a;
    ScoreEntry *entryB = (ScoreEntry *)b;
    if (entryA->score < entryB->score) return 1;
    if (entryA->score > entryB->score) return -1;
    return 0;
}

void assignRanks(ScoreEntry entries[], int n) {
    qsort(entries, n, sizeof(ScoreEntry), compare);
    int rank = 1;
    for (int i = 0; i < n; i++) {
        if (i == 0 || entries[i].score != entries[i - 1].score) {
            rank = i + 1;
        }
        printf("Score: %.2f, Rank: %d\n", entries[i].score, rank);
    }
}

int main() {
    ScoreEntry scores[] = {
        {1, 3.50}, {2, 3.65}, {3, 4.00}, {4, 3.85}, {5, 4.00}, {6, 3.65}
    };
    int n = sizeof(scores) / sizeof(scores[0]);
    assignRanks(scores, n);
    return 0;
}

using System;
using System.Collections.Generic;

class ScoreEntry {
    public int Id { get; set; }
    public double Score { get; set; }
}

class Program {
    static void AssignRanks(List<ScoreEntry> scores) {
        scores.Sort((a, b) => b.Score.CompareTo(a.Score));
        int rank = 1;
        for (int i = 0; i < scores.Count; i++) {
            if (i == 0 || scores[i].Score != scores[i - 1].Score) {
                rank = i + 1;
            }
            Console.WriteLine($"Score: {scores[i].Score:F2}, Rank: {rank}");
        }
    }

    static void Main() {
        List<ScoreEntry> scores = new List<ScoreEntry> {
            new ScoreEntry { Id = 1, Score = 3.50 },
            new ScoreEntry { Id = 2, Score = 3.65 },
            new ScoreEntry { Id = 3, Score = 4.00 },
            new ScoreEntry { Id = 4, Score = 3.85 },
            new ScoreEntry { Id = 5, Score = 4.00 },
            new ScoreEntry { Id = 6, Score = 3.65 }
        };

        AssignRanks(scores);
    }
}

The Python solution leverages sorting with a custom key to arrange the scores in descending order. The implementation manages ranks during a single pass after sorting. Python's dynamic typing and list sequences make handling and printing straightforward.

Complexity

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), for the list of ScoreEntry objects.

Try this approach in the editor

Approach 2: Approach 2: Bucket Sort with Counting

This approach uses a bucket sort strategy, particularly efficient when scores have a limited range of decimal places. This reduces the complexity substantially in scenarios where HTTP (High Throughput Processing) is required. Counting occurrences of each score allows direct assignment of ranks in descending order of scores efficiently.

Python

from collections import Counter

def rank_scores(scores, bucket_size):
    count = Counter(int(score / bucket_size) for score in scores)
    rank = 1
    for score_index in sorted(count.keys(), reverse=True):
        score = score_index * bucket_size
        for _ in range(count[score_index]):
            print(f"Score: {score:.2f}, Rank: {rank}")
        rank += count[score_index]

scores = [3.50, 3.65, 4.00, 3.85, 4.00, 3.65]
bucket_size = 0.01
rank_scores(scores, bucket_size)

Java

import java.util.HashMap;
import java.util.TreeMap;

public class BucketRanking {
    static HashMap<Integer, Integer> countScores(double[] scores, double bucketSize) {
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for (double score : scores) {
            int index = (int) (score / bucketSize);
            countMap.put(index, countMap.getOrDefault(index, 0) + 1);
        }
        return countMap;
    }

    static void assignRanks(HashMap<Integer, Integer> countMap, double bucketSize) {
        TreeMap<Integer, Integer> sortedMap = new TreeMap<>(countMap);
        int rank = 1;
        for (int index : sortedMap.descendingKeySet()) {
            int count = sortedMap.get(index);
            double score = index * bucketSize;
            for (int i = 0; i < count; i++) {
                System.out.println("Score: " + score + ", Rank: " + rank);
            }
            rank += count;
        }
    }

    public static void main(String[] args) {
        double[] scores = {3.50, 3.65, 4.00, 3.85, 4.00, 3.65};
        double bucketSize = 0.01;
        HashMap<Integer, Integer> countMap = countScores(scores, bucketSize);
        assignRanks(countMap, bucketSize);
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <vector>

std::unordered_map<int, int> countScores(const std::vector<double>& scores, double bucketSize) {
    std::unordered_map<int, int> countMap;
    for (double score : scores) {
        int index = static_cast<int>(score / bucketSize);
        countMap[index]++;
    }
    return countMap;
}

void assignRanks(const std::unordered_map<int, int>& countMap, double bucketSize) {
    int rank = 1;
    for (auto it = countMap.rbegin(); it != countMap.rend(); ++it) {
        int index = it->first;
        int count = it->second;
        double score = index * bucketSize;
        for (int i = 0; i < count; i++) {
            std::cout << "Score: " << score << ", Rank: " << rank << std::endl;
        }
        rank += count;
    }
}

int main() {
    std::vector<double> scores = {3.50, 3.65, 4.00, 3.85, 4.00, 3.65};
    double bucketSize = 0.01;
    auto countMap = countScores(scores, bucketSize);
    assignRanks(countMap, bucketSize);
    return 0;
}

JavaScript

const countScores = (scores, bucketSize) => {
  const countMap = new Map();
  scores.forEach(score => {
    const index = Math.floor(score / bucketSize);
    if (!countMap.has(index)) {
      countMap.set(index, 0);
    }
    countMap.set(index, countMap.get(index) + 1);
  });
  return countMap;
};

const assignRanks = (countMap, bucketSize) => {
  const sortedKeys = Array.from(countMap.keys()).sort((a, b) => b - a);
  let rank = 1;
  sortedKeys.forEach(index => {
    const score = index * bucketSize;
    for (let i = 0; i < countMap.get(index); i++) {
      console.log(`Score: ${score.toFixed(2)}, Rank: ${rank}`);
    }
    rank += countMap.get(index);
  });
};

const scores = [3.50, 3.65, 4.00, 3.85, 4.00, 3.65];
const bucketSize = 0.01;
const countMap = countScores(scores, bucketSize);
assignRanks(countMap, bucketSize);

#include <stdio.h>
#define MAX_SCORE 100.00
#define MIN_SCORE 0.00
#define BUCKET_SIZE 0.01
#define BUCKET_COUNT ((int)((MAX_SCORE - MIN_SCORE) / BUCKET_SIZE + 1))

void rankScores(double scores[], int n) {
    int buckets[BUCKET_COUNT] = {0};

    for (int i = 0; i < n; i++) {
        int index = (int)((scores[i] - MIN_SCORE) / BUCKET_SIZE);
        buckets[index]++;
    }

    int rank = 0;
    for (int i = BUCKET_COUNT - 1; i >= 0; i--) {
        if (buckets[i] > 0) {
            rank += 1;
            printf("Score: %.2f, Rank: %d\n", MIN_SCORE + i * BUCKET_SIZE, rank);
            rank += (buckets[i] - 1);
        }
    }
}

int main() {
    double scores[] = {3.50, 3.65, 4.00, 3.85, 4.00, 3.65};
    int n = sizeof(scores) / sizeof(scores[0]);
    rankScores(scores, n);
    return 0;
}

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static Dictionary<int, int> CountScores(double[] scores, double bucketSize) {
        var countMap = new Dictionary<int, int>();
        foreach (var score in scores) {
            int index = (int)(score / bucketSize);
            if (countMap.ContainsKey(index)) {
                countMap[index]++;
            } else {
                countMap[index] = 1;
            }
        }
        return countMap;
    }

    static void AssignRanks(Dictionary<int, int> countMap, double bucketSize) {
        var sortedKeys = countMap.Keys.OrderByDescending(key => key).ToList();
        int rank = 1;
        foreach (var index in sortedKeys) {
            double score = index * bucketSize;
            for (int i = 0; i < countMap[index]; i++) {
                Console.WriteLine($"Score: {score:F2}, Rank: {rank}");
            }
            rank += countMap[index];
        }
    }

    static void Main() {
        double[] scores = { 3.50, 3.65, 4.00, 3.85, 4.00, 3.65 };
        double bucketSize = 0.01;
        var countMap = CountScores(scores, bucketSize);
        AssignRanks(countMap, bucketSize);
    }
}

Python uses a Counter from the collections module to tally the scores into bucketed indices. It then processes these counts in descending order of buckets to output ranks efficiently. This bucket implementation relies on Python's ability to handle large integers and dynamic indexing smartly.

Complexity

Time Complexity: O(n + k log k), from counting and sorting.
Space Complexity: O(k), determined by count of unique score groups.

Try this approach in the editor

Approach 3: Default Approach

MySQL

# Write your MySQL query statement below
SELECT
    score,
    DENSE_RANK() OVER (ORDER BY score DESC) AS 'rank'
FROM Scores;

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Sorting and Rank Assignment	Time Complexity: O(n log n), due to sorting. Space Complexity: O(n), for the list of ScoreEntry objects.
Approach 2: Bucket Sort with Counting	Time Complexity: O(n + k log k), from counting and sorting. Space Complexity: O(k), determined by count of unique score groups.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Sorting and Rank Assignment	O(n log n)	O(n)	General case where score range is unknown or large
Bucket Sort with Counting	O(n + k)	O(k)	When score values fall within a limited numeric range

Frequently asked questions

Is Rank Scores easy or hard?

Rank Scores is generally considered a medium-level problem. The logic is simple once you understand dense ranking, but recognizing how to handle duplicates without skipping rank numbers can confuse beginners.

Rank Scores Python/Java solution

Python and Java solutions typically sort the scores in descending order, then iterate while tracking the previous score and current rank. Whenever the score changes, the rank increases. Duplicate scores reuse the same rank value.

How to solve Rank Scores in O(n)?

An O(n) style solution is possible using bucket counting if the score values fall within a limited range. You count the frequency of each score and iterate from highest to lowest to assign ranks. This removes the need for comparison-based sorting.

What is the best approach for Rank Scores?

Sorting the scores in descending order and assigning ranks while tracking duplicates is the most practical approach. It runs in O(n log n) time and works regardless of score range. For database solutions, the equivalent concept is a dense ranking operation.

Is Rank Scores asked at Google/Amazon/Meta?

Ranking and dense ranking problems appear in interviews at companies that test database and data processing skills. Variations of this problem often appear in SQL interview rounds at companies like Amazon, Meta, and fintech firms.

What data structure is used in Rank Scores?

The most common solution uses arrays or lists combined with sorting. An optimized approach uses a counting array or bucket structure to track score frequencies before assigning ranks.

What is the time complexity of Rank Scores?

The typical implementation using sorting takes O(n log n) time because the dataset must be ordered before ranks are assigned. A bucket or counting-based optimization can reduce this to O(n + k) when the score range is small.

Rank Scores solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sorting and Rank Assignment

Approach 2: Approach 2: Bucket Sort with Counting

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Rank Scores solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sorting and Rank Assignment

Approach 2: Approach 2: Bucket Sort with Counting

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems