LeetCode Problem 1244

Difficulty: 🟡 Medium
Topics: Hash Table, Design, Sorting

Solution

LeetCode 1244 - Design A Leaderboard

Problem Understanding

This problem asks us to design a leaderboard system that supports three operations efficiently. Each player has a unique playerId and an associated score. The leaderboard begins empty, and players can be added dynamically as operations are performed.

The addScore(playerId, score) operation either creates a new player with the given score or increases the score of an existing player. The top(K) operation returns the sum of the highest K scores currently present in the leaderboard. The reset(playerId) operation removes a player's score by resetting it to zero, effectively deleting them from the active leaderboard.

The input consists of a sequence of method calls and arguments. The expected output is the result returned by each operation that produces a value, specifically the top() operation. Methods that modify the leaderboard without returning anything produce null in the example output.

The constraints are important for choosing the implementation strategy:

• There are at most 1000 function calls.
• playerId and K are at most 10000.
• Individual score increments are small, at most 100.

The small number of total operations means we do not necessarily need highly sophisticated balanced tree structures or heaps with lazy deletion. A straightforward and clean solution using hash maps and sorting is completely acceptable within the problem limits.

Several edge cases are important to recognize early:

• A player may receive multiple score updates over time.
• Multiple players may have the same score.
• Reset removes a player completely from consideration.
• top(K) is guaranteed to have at least K active players.
• The leaderboard starts empty, so implementations must correctly initialize internal data structures.

Approaches

Brute Force Approach

The simplest possible implementation stores every player's current score in a hash map. Whenever top(K) is called, we collect all scores into a list, sort them in descending order, and sum the first K values.

This approach is correct because sorting guarantees that the largest scores appear first, so taking the first K elements produces the exact answer required.

The downside is that every top(K) query performs a full sort over all active players. If the number of players becomes large, repeated sorting becomes inefficient.

Still, because the constraint limits total operations to only 1000, this solution is actually fast enough for LeetCode.

Optimized Approach

A better approach maintains two data structures:

1. A hash map from playerId to current score.
2. A sorted multiset structure storing all current scores.

When a player's score changes, we remove the old score from the sorted structure and insert the updated score. Then top(K) can iterate over the largest scores directly without re-sorting everything each time.

In languages with built-in balanced trees or sorted containers, this approach improves repeated query efficiency. However, implementing a true balanced tree manually is unnecessary here.

For LeetCode, the practical optimal solution is usually considered the hash map plus sorting approach because the constraints are intentionally small.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N log N) for top, O(1) updates	O(N)	Sort scores during every top() call
Optimal	O(N log N) worst case overall operations	O(N)	Hash map for scores, sorting only when needed

Algorithm Walkthrough

Optimal Strategy Using Hash Map and Sorting

1. Initialize a hash map called player_scores.

The key is the player ID, and the value is the player's current total score. This gives constant time access for updates and resets. 2. For addScore(playerId, score):

• If the player already exists, add the new score to the existing total.
• Otherwise, create a new entry with the given score.

A hash map is ideal here because player lookup and updates are average O(1) operations. 3. For top(K):

• Extract all score values from the hash map.
• Sort them in descending order.
• Sum the first K values.

Sorting guarantees that the highest scores appear first. 4. For reset(playerId):

• Remove the player from the hash map entirely.

Since the problem defines reset as erasing the player from the leaderboard, deletion is more appropriate than setting the score to zero.

Why it works

The core invariant is that the hash map always stores the exact current score for every active player. Because top(K) sorts the complete set of current scores before selecting the largest K, it always computes the correct leaderboard sum. Updates and resets modify the hash map immediately, ensuring that all future queries operate on the latest state.

Python Solution

class Leaderboard:

    def __init__(self):
        self.player_scores = {}

    def addScore(self, playerId: int, score: int) -> None:
        if playerId in self.player_scores:
            self.player_scores[playerId] += score
        else:
            self.player_scores[playerId] = score

    def top(self, K: int) -> int:
        sorted_scores = sorted(
            self.player_scores.values(),
            reverse=True
        )

        return sum(sorted_scores[:K])

    def reset(self, playerId: int) -> None:
        del self.player_scores[playerId]

# Your Leaderboard object will be instantiated and called as such:
# obj = Leaderboard()
# obj.addScore(playerId, score)
# param_2 = obj.top(K)
# obj.reset(playerId)

The implementation begins by initializing an empty dictionary called player_scores. This dictionary acts as the central source of truth for all active players and their scores.

The addScore method checks whether the player already exists. If so, the score is incremented. Otherwise, a new player entry is created.

The top method extracts all current scores using values(), sorts them in descending order, and sums the first K entries. Python's built-in sorting is efficient and concise, making the implementation straightforward.

The reset method removes the player completely using del. This ensures the player no longer contributes to future leaderboard calculations.

Go Solution

package main

import "sort"

type Leaderboard struct {
	playerScores map[int]int
}

func Constructor() Leaderboard {
	return Leaderboard{
		playerScores: make(map[int]int),
	}
}

func (this *Leaderboard) AddScore(playerId int, score int) {
	this.playerScores[playerId] += score
}

func (this *Leaderboard) Top(K int) int {
	scores := make([]int, 0, len(this.playerScores))

	for _, score := range this.playerScores {
		scores = append(scores, score)
	}

	sort.Sort(sort.Reverse(sort.IntSlice(scores)))

	total := 0

	for i := 0; i < K; i++ {
		total += scores[i]
	}

	return total
}

func (this *Leaderboard) Reset(playerId int) {
	delete(this.playerScores, playerId)
}

/**
 * Your Leaderboard object will be instantiated and called as such:
 * obj := Constructor()
 * obj.AddScore(playerId, score)
 * param_2 := obj.Top(K)
 * obj.Reset(playerId)
 */

The Go implementation mirrors the Python solution closely. A map from integer player IDs to scores provides efficient updates and lookups.

One important Go-specific detail is that map access automatically returns zero for missing keys. This allows AddScore to use:

this.playerScores[playerId] += score

without checking whether the player already exists.

For sorting, Go requires explicitly constructing a slice of scores and then applying sort.Sort(sort.Reverse(sort.IntSlice(scores))) to obtain descending order.

The delete built-in cleanly removes players during reset operations.

Worked Examples

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]]

Step-by-step Trace

Operation	Leaderboard State	Result
addScore(1, 73)	{1: 73}
addScore(2, 56)	{1: 73, 2: 56}
addScore(3, 39)	{1: 73, 2: 56, 3: 39}
addScore(4, 51)	{1: 73, 2: 56, 3: 39, 4: 51}
addScore(5, 4)	{1: 73, 2: 56, 3: 39, 4: 51, 5: 4}
top(1)	Scores sorted: [73, 56, 51, 39, 4]	73
reset(1)	{2: 56, 3: 39, 4: 51, 5: 4}
reset(2)	{3: 39, 4: 51, 5: 4}
addScore(2, 51)	{2: 51, 3: 39, 4: 51, 5: 4}
top(3)	Scores sorted: [51, 51, 39, 4]	141

The final answer is 141 because the top three scores are 51, 51, and 39.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N log N) for top()	Sorting all active scores dominates runtime
Space	O(N)	Hash map stores all active players

The addScore and reset operations both run in average constant time because hash map operations are efficient. The expensive operation is top(K), which sorts all current player scores. If there are N active players, sorting requires O(N log N) time.

The space complexity is linear because we store one hash map entry per active player.

Test Cases

# Example case from problem statement
lb = Leaderboard()
lb.addScore(1, 73)
lb.addScore(2, 56)
lb.addScore(3, 39)
lb.addScore(4, 51)
lb.addScore(5, 4)
assert lb.top(1) == 73  # highest score

lb.reset(1)
lb.reset(2)

lb.addScore(2, 51)
assert lb.top(3) == 141  # top three scores

# Single player leaderboard
lb = Leaderboard()
lb.addScore(10, 100)
assert lb.top(1) == 100  # only one player

# Multiple updates to same player
lb = Leaderboard()
lb.addScore(1, 20)
lb.addScore(1, 30)
assert lb.top(1) == 50  # accumulated score

# Reset removes player
lb = Leaderboard()
lb.addScore(1, 40)
lb.addScore(2, 60)
lb.reset(2)
assert lb.top(1) == 40  # player 2 removed

# Equal scores
lb = Leaderboard()
lb.addScore(1, 50)
lb.addScore(2, 50)
lb.addScore(3, 50)
assert lb.top(2) == 100  # duplicate top scores

# Large K equals number of players
lb = Leaderboard()
lb.addScore(1, 10)
lb.addScore(2, 20)
lb.addScore(3, 30)
assert lb.top(3) == 60  # sum all players

# Re-adding reset player
lb = Leaderboard()
lb.addScore(1, 70)
lb.reset(1)
lb.addScore(1, 15)
assert lb.top(1) == 15  # player starts fresh after reset

Test	Why
Example input	Validates overall functionality
Single player	Smallest practical leaderboard
Multiple updates	Confirms score accumulation
Reset player	Ensures removal works correctly
Equal scores	Verifies duplicate values are handled
K equals player count	Ensures full leaderboard summation
Re-adding player	Confirms reset fully clears prior score

Edge Cases

Repeated score additions for the same player

One common source of bugs is incorrectly overwriting a player's score instead of accumulating it. The problem explicitly states that addScore adds to the existing score. The implementation handles this by incrementing the current value rather than replacing it.

Resetting a player and adding them again

After reset, a player should behave like a completely new player if added again later. Some implementations mistakenly leave stale data behind. This solution removes the player from the hash map entirely, so future additions begin from zero naturally.

Multiple players with identical scores

Leaderboards often contain ties. A flawed implementation might accidentally deduplicate equal values during sorting or storage. Since this solution stores scores independently per player and sorts raw score values, equal scores are counted correctly and independently during top(K) calculations.