Kth Largest Element in a Stream

Problem

Design a class KthLargest that tracks the k-th largest value in a growing stream of integers, counting duplicates as separate entries.

• KthLargest(k, nums) initializes the tracker with an integer k and an initial list nums (possibly empty).
• add(val) appends val to the stream and returns the current k-th largest value.

It is guaranteed that by the time add is called there are at least k values in the stream.

• k and the size of the initial list are each bounded by roughly ten thousand.
• Values fit comfortably in a normal int, positive or negative.
• Up to about ten thousand calls to add.

Examples

• KthLargest(3, [6, 7, 10, 3]), then add(5) → 6, add(11) → 7, add(15) → 10, add(12) → 11, add(6) → 11. Each new value that beats the current 3rd-largest bumps the threshold up.
• KthLargest(1, []), then add(-5) → -5, add(-1) → -1, add(-8) → -1. With k = 1 the tracker simply reports the running maximum.
• KthLargest(2, [9, 9]), then add(2) → 9. Duplicates count separately, so the 2nd largest is the second 9.

Hints

1. You only ever need to answer questions about the top k values. Everything smaller is irrelevant forever. Why?
2. Among the top k, which single value do you need instant access to, and which value do you need to evict when a new one arrives?
3. Keep a min-heap of exactly k elements; its root is the answer, and each add pushes then pops if the size exceeds k.