Maintain the Kth-Highest User Score with Updates and Removals

Problem Statement

Design a class ScoreTracker that maintains a collection of user scores and allows for real-time tracking of the k-th highest score. You must handle updates to existing scores and the removal of scores. If the number of users in the system is less than k, the tracker should return null.

Class Interface

class ScoreTracker:
    def __init__(self, k: int):
        # Initialize with the value k
        pass

    def add_score(self, user_id: int, score: int) -> None:
        # Add a new user with a specific score
        pass

    def update_score(self, user_id: int, new_score: int) -> None:
        # Update the score of an existing user
        pass

    def remove_user(self, user_id: int) -> None:
        # Remove a user from the system
        pass

    def get_kth_highest(self) -> Optional[int]:
        # Return the k-th highest score, or None if not enough users
        pass

Constraints

• 1 <= k <= 10^5
• Total number of users N will not exceed 10^5.
• Scores are integers.
• Multiple users can have the same score; each instance should be tracked independently.

Example

tracker = ScoreTracker(2)
tracker.add_score(1, 10)
tracker.add_score(2, 20)
tracker.add_score(3, 15)
print(tracker.get_kth_highest()) # Output: 15 (Scores: 20, 15, 10)

tracker.update_score(3, 5)
print(tracker.get_kth_highest()) # Output: 10 (Scores: 20, 10, 5)

Edge Cases

• Updating a user score that doesn't exist.
• Removing a user who doesn't exist.
• Calling get_kth_highest when there are fewer than k users.