Kth Largest Element in a Stream

Design a class that tracks the k-th largest value of a stream (by sorted order, duplicates count):

• KthLargest(k, nums) starts with the numbers in nums.
• add(val) adds val to the stream and returns the current k-th largest value.

Example 1

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

After adding 3 the values are [2,3,4,5,8]; the 3rd largest is 4. After adding 5: [2,3,4,5,5,8] → 5, and so on.

Example 2

Input:
["KthLargest", "add", "add", "add", "add"]
[[1, []], [-3], [-2], [-4], [0]]
Output: [None, -3, -2, -2, 0]

Example 3

Input:
["KthLargest", "add", "add", "add"]
[[2, [0]], [-1], [1], [-2]]
Output: [None, -1, 0, 0]

Constraints

• 1 <= k <= 10^4, 0 <= len(nums) <= 10^4
• -10^5 <= nums[i], val <= 10^5
• At most 10^4 calls to add
• There are at least k values whenever add returns