Domain 2MediumMEDIUM

Design A Leaderboard

Uses a hash map for O(1) score updates and sorting values to efficiently calculate top-K sums, leveraging low operation count constraints.

Domain: medium•Updated: 2026-09-11
#hash map#sorting#O(N log N)#dictionary

Problem Breakdown

We need to implement a dynamic data structure that manages scores for multiple players and supports three specific operations efficiently:

  1. addScore(playerId, score): Increment an existing player’s total or initialize them if they don’t exist yet.
  2. top(K): Calculate the sum of the highest K current scores in the system.
  3. reset(playerId): Remove a specific player from consideration (effectively setting their score to zero and excluding them).

Key Constraints & Edge Cases:

  • Scale: Up to 10,000 players (playerId) but only up to 1,000 total function calls. This suggests we don’t need highly optimized data structures like heaps or Fenwick trees for every operation; a standard dictionary with sorting is likely sufficient given the low call frequency relative to N.
  • Reset Guarantee: The problem guarantees reset will be called only if the player exists, so no error handling needed there (though defensive checks are safe).
  • Empty State: If top(K) is called when fewer than K players exist (or leaderboard empty), we sum all available scores. Note that constraints say K≤K \le current number of players, so we never ask for more top items than exist.

Intuition

A brute-force approach would be to store the list in an array and sort it every time top(K) is called. However, since we need frequent updates (addScore, reset), maintaining a sorted list directly (like inserting into a BST) adds overhead (O(N)O(N) or O(log⁡N)O(\log N) per update).

The Key Insight: We can separate concerns:

  1. Storage & Updates: Use a Hash Map (Python Dictionary) for O(1) access to store playerId -> current_score. This handles addScore and reset efficiently without touching the sorted structure immediately.
  2. Querying (top(K)): Since we only need the sum of top K scores, sorting the values from our dictionary is acceptable given the constraints (N=10k). Python’s Timsort is highly optimized for partially sorted data and runs in O(Nlog⁡N)O(N \log N). With a maximum of 1,000 calls to top, total complexity remains well within limits.

If we were optimizing strictly for high-frequency updates vs queries on massive datasets (N>105N > 10^5), we might consider heaps or segment trees, but here the dictionary + sort approach is cleaner and idiomatic in Python.

Approach

  1. Initialization: Create a class Leaderboard with an instance variable (e.g., self.scores) initialized as an empty hash map ({}).
  2. addScore(playerId, score):
    • Check if playerId exists in the dictionary using .get().
    • If it does not exist, initialize with score.
    • If it exists, add score to the existing value (self.scores[playerId] += score).
  3. reset(playerId):
    • Remove the key from the dictionary using .pop(). This effectively removes them from future sums and keeps memory usage proportional to active players.
  4. top(K):
    • Extract all current scores into a list: list(self.scores.values()).
    • Sort this list in descending order (reverse=True).
    • Sum the first K elements using slicing or iteration. Return the sum (defaulting to 0 if empty, though constraints ensure K is valid).

Complexity Analysis

  • Time Complexity:
    • addScore: O(1)O(1) average case for dictionary operations.
    • reset: O(1)O(1) amortized with .pop().
    • top(K): Sorting takes O(Nlog⁡N)O(N \log N) where NN is the number of active players (≤10,000\le 10,000). With a maximum of 1,000 calls to this method across all test cases (implied by “at most 1000 function calls”), total operations are roughly proportional to acceptable limits for Python.
  • Space Complexity: O(N)O(N) where NN is the number of unique players stored in the dictionary.

Solution

class Leaderboard:
    def __init__(self):
        self.scores = {}  # Dictionary mapping playerId -> current total score
    
    def addScore(self, playerId: int, score: int) -> None:
        if playerId not in self.scores:
            self.scores[playerId] = score
        else:
            self.scores[playerId] += score
            
    def top(self, K: int) -> int:
        # Extract current scores and sort descending to get highest first
        sorted_scores = sorted(list(self.scores.values()), reverse=True)
        
        # Sum the top K elements. 
        # Constraints guarantee K <= len(sorted_scores), so slicing is safe.
        return sum(sorted_scores[:K])

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

Edge Cases Handled

  • New Player: addScore handles initialization via the dictionary’s default behavior (check existence before adding).
  • Existing Player Update: Logic correctly increments existing scores rather than overwriting.
  • Reset Guarantee: The prompt guarantees a player exists for reset; using .pop() or explicit deletion removes them cleanly from memory and logic without needing to check if they exist first in the implementation (though checking is safer generally).
  • Top K Summation: Slicing [:K] handles cases where fewer than K players might theoretically remain, though constraints prevent this. It returns 0 for empty lists naturally via Python’s sum behavior on an empty sequence.