Kth Highest Score in a Live Gaming Leaderboard

Problem Statement

A live gaming leaderboard receives a continuous stream of match scores. At any point, the product team wants to know the Kth highest score seen so far (e.g., the cutoff to be in the top 10).

Design a class:

• LiveLeaderboard(k, initialScores) — initialize with K and any starting scores
• add(score) — record a new score and return the current Kth highest

Constraints

• 1 <= k <= 10^4
• Scores arrive one at a time, potentially millions
• add should be efficient (better than re-sorting every time)

Example

LiveLeaderboard(3, [4, 5, 8, 2])
add(3)   // scores: 8,5,4,3,2 → 3rd highest = 4
add(5)   // scores: 8,5,5,4,3,2 → 3rd highest = 5
add(10)  // 3rd highest = 5
add(9)   // 3rd highest = 8
add(4)   // 3rd highest = 8

The Insight — Min-Heap of Size K

The naive approach keeps all scores sorted and indexes the Kth — O(n log n) per add. The elegant trick: you only ever care about the top K scores, so maintain a min-heap of exactly size K.

Why a MIN-heap for the Kth LARGEST?

• The heap holds the K largest scores seen so far.
• The smallest of those K (the heap's root) IS the Kth largest overall.
• On add: push the new score. If the heap exceeds size K, pop the minimum. The root is always your answer.

add(score):
    heap.push(score)
    if heap.size > k: heap.pop()   # drop the smallest
    return heap.peek()             # root = Kth largest

Each add is O(log K), not O(log n). The counter-intuitive "use a MIN-heap to track the MAX-Kth" is the insight that trips people up and then delights them once it clicks.

Follow-ups

1. Why does the minimum of the top-K equal the Kth largest overall?
2. What if scores could be removed (a player's score gets revoked)?
3. How would you get the full top-K list, not just the Kth?
4. How would you scale this to a distributed leaderboard across regions?