#164EasyHeaps· Bounded Min-Heap

Kth Largest Score Tracker

A game shows a live leaderboard banner with the score that currently sits in position `k` from the top: the **k-th largest** score so far, counting equal scores separately. Scores keep arriving, and the banner must update after each one without re-sorting the entire history. Design a class `KthLargestScoreTracker`: - `KthLargestScoreTracker(k, scores)` starts the tracker with the integer `k` and the initial scores. - `add(score)` records a new score and returns the current k-th largest score. It is guaranteed that after every call to `add` at least `k` scores have been recorded.

Input format

`operations`: the method names in call order (the first is the constructor); `arguments`: the argument list of each call.

Output format

One value per operation: `null` for the constructor and the k-th largest score for each `add`.

Examples

Input: operations = ["KthLargestScoreTracker", "add", "add", "add", "add", "add"], arguments = [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

Output: [null, 4, 5, 5, 8, 8]

Start with scores 4, 5, 8, 2 and k = 3. After adding 3 the sorted scores are 8, 5, 4, 3, 2 and the 3rd largest is 4. Adding 5 gives 8, 5, 5, 4, ... so the answer becomes 5. Adding 10, 9 and 4 gives 5, 8 and 8.

Input: operations = ["KthLargestScoreTracker", "add", "add", "add"], arguments = [[1, []], [-3], [5], [2]]

Output: [null, -3, 5, 5]

With k = 1 the tracker returns the maximum so far: -3, then 5, then 5 again.

Constraints

1 <= k <= 10^4
0 <= scores.length <= 10^4
-10^4 <= score <= 10^4
At most 10^4 calls to `add`
After every `add` at least k scores have been recorded.

Study first

Heaps and Priority Queues

#heap
#priority-queue
#design
#streaming