Running Kth Highest Score
A leaderboard starts with the scores in initial. Then the scores in additions arrive one at a time.
After each arrival, report the k-th highest score seen so far (counting duplicates separately). If fewer than k scores have been seen, report null. Return the list of reports.
Keep a min-heap of the k best scores instead of sorting after every arrival; you will need to write the heap yourself.
Example 1
Input: k = 3, initial = [4,5,8,2], additions = [3,5,10,9,4] Output: [4,5,5,8,8] Explanation: The 3rd highest after adding 3 is 4, after adding 5 it is 5, and so on.
Example 2
Input: k = 1, initial = [], additions = [-1,1,-2,-4,3] Output: [-1,1,1,1,3] Explanation: With k = 1 each report is the maximum so far.
Constraints
- 1 <= k <= 10^4
- 0 <= initial.length <= 10^4
- 1 <= additions.length <= 2 * 10^4
- -10^6 <= score <= 10^6
Hint 1
A min-heap holding the k largest scores has the k-th largest at its top.
Hint 2
When a new score beats the top, pop the top and push the new score.
Discussion 0
Join free to post in the discussion.
Good practice for: Game Developer, Backend Developer, Full Stack Developer, Mobile App Developer, Data Engineer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.