Kth largest score in a stream

Scenario

An online exam portal shows a live "cut-off" line while students submit their papers. The cut-off is the score of the student at rank k: the kth highest score so far.

Scores arrive one at a time, and the portal must update the cut-off after every score. Up to 100,000 students take the exam, so sorting all the scores again after each new one would be too slow.

Your task

Write kth_scores(k, scores).

scores[i] is the score of the student who submits ith, in the order they arrive.
After each score arrives, find the kth highest score among all scores so far. Equal scores count separately.
If fewer than k scores have arrived, the answer for that step is -1.
Return the list of answers, one for each arrival.

Examples

Example 1 (traced)#

text2 lines

Input:  k = 3, scores = [4, 5, 8, 2, 3, 10]
Output: [-1, -1, 4, 4, 4, 5]

New score	Three best so far	Answer
4	4	-1 (only 1 score)
5	4, 5	-1 (only 2 scores)
8	4, 5, 8	4
2	4, 5, 8 (2 is too small)	4
3	4, 5, 8 (3 is too small)	4
10	5, 8, 10 (4 drops out)	5

The answer is the smallest of the three best scores.

Example 2#

text2 lines

Input:  k = 1, scores = [3, 1, 7, 2]
Output: [3, 3, 7, 7]

With k = 1 the cut-off is the highest score so far, so it only changes when a new highest score arrives.

Example 3#

text2 lines

Input:  k = 2, scores = [9]
Output: [-1]

One score has arrived, and the portal needs two before it can name the 2nd highest.

Constraints

1 ≤ k ≤ 10^5
1 ≤ length of scores ≤ 10^5
0 ≤ scores[i] ≤ 10^6

What does n ≤ 10^5 tell you?

A portal with 100,000 scores that sorted all the scores so far after each arrival would sort up to 100,000 numbers, 100,000 times. That is billions of steps.

You only need the k best scores, and their smallest is the answer. A heap of size k holds exactly that, and each new score costs about log k steps.

Scenario

An online exam portal shows a live "cut-off" line while students submit their papers. The cut-off is the score of the student at rank k: the kth highest score so far.

Scores arrive one at a time, and the portal must update the cut-off after every score. Up to 100,000 students take the exam, so sorting all the scores again after each new one would be too slow.

Your task

Write kth_scores(k, scores).

scores[i] is the score of the student who submits ith, in the order they arrive.
After each score arrives, find the kth highest score among all scores so far. Equal scores count separately.
If fewer than k scores have arrived, the answer for that step is -1.
Return the list of answers, one for each arrival.

Examples

Example 1 (traced)#

text2 lines

Input:  k = 3, scores = [4, 5, 8, 2, 3, 10]
Output: [-1, -1, 4, 4, 4, 5]

New score	Three best so far	Answer
4	4	-1 (only 1 score)
5	4, 5	-1 (only 2 scores)
8	4, 5, 8	4
2	4, 5, 8 (2 is too small)	4
3	4, 5, 8 (3 is too small)	4
10	5, 8, 10 (4 drops out)	5

The answer is the smallest of the three best scores.

Example 2#

text2 lines

Input:  k = 1, scores = [3, 1, 7, 2]
Output: [3, 3, 7, 7]

With k = 1 the cut-off is the highest score so far, so it only changes when a new highest score arrives.

Example 3#

text2 lines

Input:  k = 2, scores = [9]
Output: [-1]

One score has arrived, and the portal needs two before it can name the 2nd highest.

Constraints

1 ≤ k ≤ 10^5
1 ≤ length of scores ≤ 10^5
0 ≤ scores[i] ≤ 10^6

What does n ≤ 10^5 tell you?

A portal with 100,000 scores that sorted all the scores so far after each arrival would sort up to 100,000 numbers, 100,000 times. That is billions of steps.

You only need the k best scores, and their smallest is the answer. A heap of size k holds exactly that, and each new score costs about log k steps.