Editorial for K-th Smallest Stream

Approach

We want the $k$-th smallest after each prefix. A direct sort of every prefix is too slow.

Keep a max-heap containing exactly the $k$ smallest values seen so far.

• If the heap has fewer than $k$ values, push the new value.
• Otherwise, compare the new value to the largest inside this set (the heap top).
  • If the new value is smaller, it belongs in the $k$ smallest set, so replace the top.
  • Otherwise ignore it.

Then:

• if heap size is less than $k$, answer is -1;
• else the heap top is the current $k$-th smallest.

In Python, heapq is a min-heap, so we store negatives to simulate a max-heap.

Time complexity is $O(n \log k)$.

Solution (Python)

import heapq

n, k = map(int, input().split())
values = list(map(int, input().split()))

heap = []
answers = []

for x in values:
    if len(heap) < k:
        heapq.heappush(heap, -x)
    elif x < -heap[0]:
        heapq.heapreplace(heap, -x)

    if len(heap) < k:
        answers.append("-1")
    else:
        answers.append(str(-heap[0]))

print("\n".join(answers))