Kth Largest Element in a Stream

Design a system to find the kth largest element in a stream of numbers.

You are given an integer k, an initial array of integers nums, and an array additions representing new numbers added to the stream one at a time. For each addition, return the kth largest element in the stream after that number is added.

Note: The kth largest element is the kth largest in sorted order, not the kth distinct element.

Examples

Example 1:

Input: k = 3, nums = [4,5,8,2], additions = [3,5,10,9,4]

Output: [4,5,5,8,8]

Explanation:

• Add 3: stream = [2,3,4,5,8], 3rd largest = 4
• Add 5: stream = [2,3,4,5,5,8], 3rd largest = 5
• Add 10: stream = [2,3,4,5,5,8,10], 3rd largest = 5
• Add 9: stream = [2,3,4,5,5,8,9,10], 3rd largest = 8
• Add 4: stream = [2,3,4,4,5,5,8,9,10], 3rd largest = 8

Example 2:

Input: k = 1, nums = [], additions = [1,2,3]

Output: [1,2,3]

Explanation:

• Add 1: stream = [1], 1st largest = 1
• Add 2: stream = [1,2], 1st largest = 2
• Add 3: stream = [1,2,3], 1st largest = 3

Example 3:

Input: k = 2, nums = [5,3], additions = [1,4,6]

Output: [3,4,5]

Explanation:

• Add 1: stream = [1,3,5], 2nd largest = 3
• Add 4: stream = [1,3,4,5], 2nd largest = 4
• Add 6: stream = [1,3,4,5,6], 2nd largest = 5

Constraints

• 1 <= k <= nums.length + 1
• 0 <= nums.length <= 10⁴
• -10⁴ <= nums[i] <= 10⁴
• 1 <= additions.length <= 10⁴
• -10⁴ <= additions[i] <= 10⁴
• It is guaranteed that there will be at least k elements in the stream when each add is called.