Description
Design a class to find the kth largest element in a stream of numbers. Implement methods to initialize with k and a list of numbers, and to add a new number while returning the current kth largest.
Examples
Input:
k = 3, nums = [4,5,8,2], stream = [[3],[5],[10]]Output:
[4,5,5]Explanation:
Initial array sorted: [2,3,4,5,8]. After add(3): sorted [2,3,3,4,5,8], 3rd largest is 4. After add(5): sorted [2,3,3,4,5,5,8], 3rd largest is 5. After add(10): sorted [2,3,3,4,5,5,8,10], 3rd largest is 5.
Input:
k = 3, nums = [4,5,8,2], stream = [[1]]Output:
[4]Explanation:
After adding 1 to [4,5,8,2], the sorted array is [1,2,4,5,8]. The 3rd largest element is 4.
Input:
k = 2, nums = [1], stream = [[7],[3],[9],[2]]Output:
[1,3,7,7]Explanation:
Starting with nums=[1] and k=2. After adding 7: [1,7] → 2nd largest is 1. After adding 3: [1,3,7] → 2nd largest is 3. After adding 9: [1,3,7,9] → 2nd largest is 7. After adding 2: [1,2,3,7,9] → 2nd largest is still 7.
Constraints
- •
1 ≤ k ≤ 10⁴