Kth Largest Element in a Stream

Design a class that, given k and an initial list of scores, keeps returning the k-th largest score as new scores arrive.

• KthLargest(k, nums) initialises with the scores in nums.
• add(val) adds val and returns the current k-th largest value.

Examples

Input:  ["KthLargest","add","add","add","add","add"]
        [[3,[4,5,8,2]],[3],[5],[10],[9],[4]]
Output: [null,4,5,5,8,8]

Constraints

• 1 ≤ k ≤ 10⁴, 0 ≤ nums.length ≤ 10⁴; there are always at least k values when add returns.

Explanation

Sorting every time

Keep all values in a list and sort after each add: O(n log n) per call. Too slow for a stream.

Keep only the top k in a min-heap

The k-th largest is the smallest of the k largest values. So keep exactly those k values in a min-heap:

• Push the new value.
• If the heap has more than k values, pop the smallest; it can never be the k-th largest again.
• The heap’s top is the answer.

Complexity

• add: O(log k). Constructor: O(n log k). Space: O(k).