Skip to main content
Talentd

Design A Leaderboard - Video Solutions

MediumHash TableDesignSorting
Practice this problemRead Solution

Leetcode 1244: Design A Leaderboard

Algorithms Casts
12:066,306 views
4 video solutions available

Design A Leaderboard - Video Solution

Watch 4 video solutions for Design A Leaderboard, a medium level problem involving Hash Table, Design, Sorting. This walkthrough by Algorithms Casts has 6,306 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.

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.
Read full problem with examples

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.

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

Continue Learning

Practice this problem

Solve it on FleetCode

Read Solution & Explanation

Detailed text walkthrough