Chef maintains a changing collection of integer values, such as scores, ranks, or performance numbers.
Initially, the collection may already contain some values. After that, new values may be inserted one by one.
At any point, Chef may be asked to find the current k-th largest value in the collection. Unlike a version where k is fixed, here k can be different for different queries.
Your task is to support insert operations and find operations on this dynamic collection.
Method Signature
Initialize
KthLargestElement(List<Integer> initialValues)
initialValues is the initial list of values.- The list may be empty.
- Values may contain duplicates.
Insert Value
void insert(int value)
value is the new value to add to the collection.- After insertion, this value must be considered in all future find operations.
Find Kth Largest
int findKthLargest(int k)
k represents which largest value should be returned.k = 1 means the largest value.k = 2 means the second largest value.- Duplicate values are counted separately.
- It is guaranteed that
1 ≤ k ≤ current number of values in the collection.
Constraints
0 ≤ initialValues.size() ≤ 105-106 ≤ initialValues[i] ≤ 106-106 ≤ value ≤ 1061 ≤ k ≤ current number of values in the collection1 ≤ total number of insert and findKthLargest calls ≤ 105
Examples
Example 1
KthLargestElement(initialValues = [5, 2, 8])
findKthLargest(k = 1) returns 8
findKthLargest(k = 3) returns 2
insert(value = 6)
findKthLargest(k = 2) returns 6
insert(value = 10)
findKthLargest(k = 1) returns 10
Explanation: Initially, the values are [5, 2, 8]. The largest value is 8, and the third largest value is 2. After inserting 6, the sorted order from largest to smallest is [8, 6, 5, 2], so the second largest value is 6. After inserting 10, the largest value becomes 10.
Example 2
KthLargestElement(initialValues = [4, 4, 9, 1])
findKthLargest(k = 2) returns 4
insert(value = 4)
findKthLargest(k = 3) returns 4
insert(value = 12)
findKthLargest(k = 2) returns 9
findKthLargest(k = 5) returns 4
Explanation: Duplicate values are counted separately. Initially, the values in descending order are [9, 4, 4, 1]. After another 4 is inserted, the descending order is [9, 4, 4, 4, 1]. After inserting 12, the descending order is [12, 9, 4, 4, 4, 1].
Example 3
KthLargestElement(initialValues = [])
insert(value = 7)
findKthLargest(k = 1) returns 7
insert(value = -3)
insert(value = 15)
findKthLargest(k = 2) returns 7
findKthLargest(k = 3) returns -3
Explanation: The collection starts empty. After inserting 7, it is the only value, so it is the first largest. After inserting -3 and 15, the descending order is [15, 7, -3].