Design A Leaderboard - Practice Coding Problems

Design A Leaderboard - Problem

Design a Leaderboard class with three main functions:

addScore(playerId, score): Update the leaderboard by adding the given score to the player's existing score. If the player doesn't exist, add them with the given score.
top(K): Return the sum of scores of the top K players on the leaderboard.
reset(playerId): Reset the player's score to 0 (remove them from the leaderboard). The player is guaranteed to exist.

Initially, the leaderboard is empty.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["Leaderboard","addScore","addScore","top"], parameters = [[],[1,73],[2,56],[2]]

› Output: [129]

💡 Note: Create leaderboard, add player 1 with 73 points, add player 2 with 56 points, then get top 2 sum: 73 + 56 = 129

Example 2 — Multiple Updates

$ Input: operations = ["Leaderboard","addScore","addScore","addScore","top"], parameters = [[],[1,73],[2,56],[1,39],[3]]

› Output: [168]

💡 Note: Player 1 gets 73+39=112 total, player 2 has 56. Top 3 sum: 112 + 56 = 168

Example 3 — Reset Operation

$ Input: operations = ["Leaderboard","addScore","addScore","reset","top"], parameters = [[],[1,73],[2,56],[1],[1]]

› Output: [56]

💡 Note: After adding scores and resetting player 1, only player 2 remains with 56 points

Constraints

1 ≤ playerId ≤ 10⁴
1 ≤ K ≤ total number of players
1 ≤ score ≤ 100
At most 1000 calls will be made to addScore, top, and reset

Visualization

Tap to expand

Understanding the Visualization

Input Operations

Sequence of addScore, top, and reset commands

Data Management

HashMap stores player scores efficiently

Query Results

top(K) returns sum of highest K scores

Key Takeaway

🎯 Key Insight: Use HashMap for constant-time updates and sort only when querying top K scores

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is to separate data storage from querying. Use a HashMap for O(1) score updates and resets, then sort scores only when top(K) is needed. Best approach: HashMap + sort on demand. Time: O(n log n) for queries, O(1) for updates. Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with List	O(n log n)	O(n)	Store all scores in a list and sort every time we need top K
HashMap + Sort on Demand	O(n log n)	O(n)	Use HashMap for O(1) updates and sort only when needed for top(K)

Brute Force with List — Algorithm Steps

Store all scores in a list
For top(K), sort entire list in descending order
Sum first K elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Scores

Store player scores in array

Sort for Query

Sort entire array when top(K) is called

Sum Top K

Add up first K elements from sorted array

Code -

solution.c — C

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

#define MAX_PLAYERS 1000

typedef struct {
    int scores[MAX_PLAYERS];
    int playerIds[MAX_PLAYERS];
    int size;
} Leaderboard;

Leaderboard* leaderboardCreate() {
    Leaderboard* lb = (Leaderboard*)malloc(sizeof(Leaderboard));
    lb->size = 0;
    return lb;
}

void leaderboardAddScore(Leaderboard* obj, int playerId, int score) {
    for (int i = 0; i < obj->size; i++) {
        if (obj->playerIds[i] == playerId) {
            obj->scores[i] += score;
            return;
        }
    }
    obj->playerIds[obj->size] = playerId;
    obj->scores[obj->size] = score;
    obj->size++;
}

int compare(const void* a, const void* b) {
    return *(int*)b - *(int*)a; // Descending order
}

int leaderboardTop(Leaderboard* obj, int K) {
    int temp[MAX_PLAYERS];
    for (int i = 0; i < obj->size; i++) {
        temp[i] = obj->scores[i];
    }
    qsort(temp, obj->size, sizeof(int), compare);
    
    int sum = 0;
    for (int i = 0; i < K && i < obj->size; i++) {
        sum += temp[i];
    }
    return sum;
}

void leaderboardReset(Leaderboard* obj, int playerId) {
    for (int i = 0; i < obj->size; i++) {
        if (obj->playerIds[i] == playerId) {
            for (int j = i; j < obj->size - 1; j++) {
                obj->playerIds[j] = obj->playerIds[j + 1];
                obj->scores[j] = obj->scores[j + 1];
            }
            obj->size--;
            return;
        }
    }
}

int main() {
    Leaderboard* lb = leaderboardCreate();
    leaderboardAddScore(lb, 1, 73);
    leaderboardAddScore(lb, 2, 56);
    int result = leaderboardTop(lb, 2);
    printf("[%d]\n", result);
    free(lb);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Each top(K) operation requires sorting all n scores

⚡ Linearithmic

Space Complexity

O(n)

List stores all player scores

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with List — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler