925. The kth Largest So Far
Values arrive one at a time. After each arrival, print the kth largest value
among everything that has arrived so far, or none if fewer than k values
have arrived.
Duplicates count separately: among 7 7 7 the third largest is 7.
``` k = 2, arrivals 4 5 8 2 3 -> none / 4 / 5 / 5 / 5
k = 3, arrivals 1 2 3 -> none / none / 1
k = 1, arrivals 1 3 2 -> 1 / 3 / 3 ```
## What most people try first
Re-sorting everything after each arrival is O(n^2 log n). At n = 2 * 10^5
that is about 2 * 10^11.
Keeping a sorted array and inserting each arrival in place is O(n) per
arrival because of the shifting, so O(n^2), which is 4 * 10^10.
Keeping ALL the values in a max-heap and popping k - 1 of them to read the
kth is O(k log n) per arrival and destroys the heap, so everything popped
has to be pushed back.
## The method: hold exactly k, and no more
Keep a MIN-heap containing the k largest values seen so far. Its smallest
member, sitting at the top, IS the kth largest.
h = empty min-heap
for each arriving value v:
push v onto h
if size(h) > k: pop the smallest
print top of h if size(h) == k, otherwise none
## Why k is enough, argued rather than asserted
The claim is that a value once evicted can never be needed again.
The multiset of arrived values only ever GROWS. So the kth largest is
non-decreasing over time: adding a value can push the boundary up, never down.
When the heap holds k values and a new one arrives, the smallest of the
k + 1 is discarded. Every future answer is at least the current kth
largest, which is at least the discarded value. So the discarded value can
never be the answer at any later point, and nothing is lost by forgetting it.
This is the argument that licenses the bounded heap, and it is exactly the
argument that FAILS for a sliding window, where values also LEAVE and the kth
largest can move back down. That is why problem #719 needs a different
structure entirely.
Note that a max-heap of size k would be useless: its top is the LARGEST of
the k best, which is just the overall maximum. The min-heap is chosen so the
element on the boundary is the one exposed.
## The boundary that breaks a careless implementation
The order inside the loop is push, then trim, then report. Trimming before
pushing keeps k - 1 values and reports the (k-1)th largest.
The none case is decided by the heap SIZE, not by whether the heap is empty.
For k = 3 the second arrival leaves a heap of size 2 and must print none.
Values can be negative, so a running best initialised to 0 is wrong in the same way it usually is.
## Overflow
Values span -10^9 to 10^9 and nothing is added, so 32-bit integers hold
everything. The only large quantity is the number of arrivals, 2 * 10^5.
## Related problems
Problem #869 keeps the k nearest points with the same bounded heap and a
derived key, and #272 asks for the kth largest of a fixed array, where
sorting once is the right answer because nothing arrives afterwards. The
difference that makes the heap worth its complexity is that the answer is
wanted after every arrival, not once at the end.
## Cost
Time O(n log k). Space O(k).
Constraints - `1 ≤ k ≤ n ≤ 200000` - `-10^9 ≤ value ≤ 10^9`
Input
The first line contains two integers n and k.
The second line contains n values in arrival order.
Output
Print n lines, one per arrival: the kth largest value among everything that has arrived so far, or the word none if fewer than k values have arrived.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.