K-th Highest Score Live

A game shows the k-th highest score on its leaderboard. Starting scores are given, then new scores arrive one at a time. After every new score, report the current k-th highest score (a repeated score counts as separate entries).

Examples

Example 1

Input:  k = 3, scores = [4, 5, 8, 2], arrivals = [3, 5, 10, 9, 4]
Output: [4, 5, 5, 8, 8]

After the 3 arrives the scores are 8, 5, 4, 3, 2, whose third highest is 4. The 5 makes it 8, 5, 5 → 5, the 10 gives 10, 8, 5 → 5, and the 9 and the 4 both leave 10, 9, 8 → 8. That is [4, 5, 5, 8, 8].

Example 2

Input:  k = 1, scores = [], arrivals = [-3, -2, -4, 0, 4]
Output: [-3, -2, -2, 0, 4]

Constraints

k is the rank to report, scores holds the leaderboard’s starting scores and arrivals the new scores in the order they come in.

Equal scores count as separate entries. Report one number per arrival — the k-th highest score at that moment — so the answer is as long as arrivals.

How to solve it

Hint

“k-th largest in a stream” → keep only the k largest in a min-heap; the smallest of them (the heap top) is exactly the k-th largest.

Approach: Min-heap of size k

Heapify the starting scores, then pop until only k remain.
For each new score: if the heap has < k items push; else if score > top replace the top.
Report the top of the heap (peek).

Check with the example. Top 3 after adding 3: {4, 5, 8} → the 3rd highest is 4.

Complexity: O(log k) per score.

The reference solutions in all four languages are in the Solutions tab of the workspace below.