Skip to main content
Talentd

Design A Leaderboard - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableDesignSorting9 min readAsked at: Amazon, Microsoft, Uber +6
Practice this problem

Problem Statement

Design a Leaderboard class, which has 3 functions:

  1. addScore(playerId, score): Update the leaderboard by adding score to the given player's score. If there is no player with such id in the leaderboard, add him to the leaderboard with the given score.
  2. top(K): Return the score sum of the top K players.
  3. reset(playerId): Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.

Initially, the leaderboard is empty.

 

Example 1:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

Explanation: 
Leaderboard leaderboard = new Leaderboard ();
leaderboard.addScore(1,73);   // leaderboard = [[1,73]];
leaderboard.addScore(2,56);   // leaderboard = [[1,73],[2,56]];
leaderboard.addScore(3,39);   // leaderboard = [[1,73],[2,56],[3,39]];
leaderboard.addScore(4,51);   // leaderboard = [[1,73],[2,56],[3,39],[4,51]];
leaderboard.addScore(5,4);    // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]];
leaderboard.top(1);           // returns 73;
leaderboard.reset(1);         // leaderboard = [[2,56],[3,39],[4,51],[5,4]];
leaderboard.reset(2);         // leaderboard = [[3,39],[4,51],[5,4]];
leaderboard.addScore(2,51);   // leaderboard = [[2,51],[3,39],[4,51],[5,4]];
leaderboard.top(3);           // returns 141 = 51 + 51 + 39;

 

Constraints:

  • 1 <= playerId, K <= 10000
  • It's guaranteed that K is less than or equal to the current number of players.
  • 1 <= score <= 100
  • There will be at most 1000 function calls.

Approach Overview

Problem Overview: Design a leaderboard system that tracks player scores. The API supports addScore(playerId, score), top(K) to return the sum of the top K scores, and reset(playerId). The challenge is maintaining fast updates while still retrieving the highest K scores efficiently.

Approach 1: Hash Map + Sorting on Query (add: O(1), top: O(n log n), reset: O(1), space: O(n))

Store each player's score in a hash map where the key is playerId and the value is the cumulative score. addScore simply updates the map entry in constant time. For top(K), extract all scores, sort them in descending order, and sum the first K elements. reset sets the player’s score back to zero or removes the entry. This approach is easy to implement using a hash table, but the repeated sorting step makes top(K) expensive when the number of players grows.

Approach 2: Hash Map + Ordered List (add/reset: O(log n), top: O(K), space: O(n))

Maintain two structures: a hash map for fast player lookups and an ordered list (or balanced tree) containing all scores in sorted order. When addScore updates a player's score, remove the old score from the ordered structure and insert the updated score at the correct position using binary search or a tree-based structure. The top(K) operation becomes efficient: iterate over the largest K values directly and sum them in O(K). reset removes the player’s score from the ordered structure and clears it in the map. This approach combines hash table lookups with efficient sorting-style ordering to avoid repeated full sorts.

Recommended for interviews: The hash map + ordered list approach is the expected design. The brute-force sorting method shows you understand the problem, but interviewers look for incremental ordering that avoids sorting the entire dataset every time top(K) runs. Maintaining a sorted structure demonstrates stronger system design and data structure selection.

Solution

We use a hash table d to record the scores of each player, and an ordered list rank to record the scores of all players.

When the addScore function is called, we first check if the player is in the hash table d. If not, we add their score to the ordered list rank. Otherwise, we first remove their score from the ordered list rank, then add their updated score to the ordered list rank, and finally update the score in the hash table d. The time complexity is O(log n).

When the top function is called, we directly return the sum of the first K elements in the ordered list rank. The time complexity is O(K times log n).

When the reset function is called, we first remove the player from the hash table d, then remove their score from the ordered list rank. The time complexity is O(log n).

The space complexity is O(n), where n is the number of players.

Code

PythonJavaC++Rust

Python

Java

C++

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map + Sort on Queryadd: O(1), top: O(n log n), reset: O(1)O(n)Simple implementation or when top queries are rare
Hash Map + Ordered Listadd/reset: O(log n), top: O(K)O(n)Best general solution with frequent leaderboard queries

Video Solution

Leetcode 1244: Design A Leaderboard • Algorithms Casts • 6,306 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Design A Leaderboard easy or hard?
Design A Leaderboard is considered a medium difficulty problem. The API is simple, but the challenge is selecting data structures that balance update operations with efficient retrieval of the top K scores.
Design A Leaderboard Python/Java solution
Typical implementations use a dictionary or HashMap for player scores and a sorted structure like TreeMap, multiset, or sorted list. Python solutions may use bisect with a list, while Java and C++ often rely on TreeMap or multiset.
How to solve Design A Leaderboard efficiently?
Store player scores in a hash map and maintain a separate sorted structure containing the scores. On addScore, update the player's value and reposition it in the ordered structure. For top(K), iterate through the K largest scores and compute their sum.
What is the best approach for Design A Leaderboard?
The best approach uses a hash map to store player scores and an ordered list (or balanced tree) to keep scores sorted. Updates remove the old score and insert the new one in O(log n), while top(K) simply sums the largest K values in O(K). This avoids sorting the entire dataset on every query.
Is Design A Leaderboard asked at Google/Amazon/Meta?
Design-style data structure problems like Design A Leaderboard commonly appear in interviews at companies such as Amazon, Google, and Meta. They test your ability to combine hash maps with ordered data structures and reason about update/query tradeoffs.
What data structure is used in Design A Leaderboard?
The core structures are a hash table for mapping playerId to score and an ordered container such as a balanced BST, sorted list, or heap-based structure to maintain score ordering. This combination supports fast updates and efficient top-K queries.
What is the time complexity of Design A Leaderboard?
With the optimized design, addScore and reset run in O(log n) due to ordered structure updates, while top(K) runs in O(K) by iterating over the highest K scores. Space complexity is O(n) for storing all player scores.

Ready to solve this problem?

Practice Design A Leaderboard with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters