Design a class to find the kth largest integer in a stream of values, including duplicates. E.g. the 2nd largest from [1, 2, 3, 3] is 3. The stream is not necessarily sorted.
Implement the following methods:
constructor(int k, int[] nums)Initializes the object given an integerkand the stream of integersnums.int add(int val)Adds the integervalto the stream and returns thekthlargest integer in the stream.
Example 1:
Input:
["KthLargest", [3, [1, 2, 3, 3]], "add", [3], "add", [5], "add", [6], "add", [7], "add", [8]]
Output:
[null, 3, 3, 3, 5, 6]
Explanation:
KthLargest kthLargest = new KthLargest(3, [1, 2, 3, 3]);
kthLargest.add(3); // return 3
kthLargest.add(5); // return 3
kthLargest.add(6); // return 3
kthLargest.add(7); // return 5
kthLargest.add(8); // return 6Constraints:
1 <= k <= 10000 <= nums.length <= 1000-1000 <= nums[i] <= 1000-1000 <= val <= 1000- There will always be at least
kintegers in the stream when you search for thekthinteger.
Topics
Recommended Time & Space Complexity
You should aim for a solution with O(nlog(k + 1)) initialization time, O(log(k + 1)) time per add() call, and O(k) space. The total time is O((n + m)log(k + 1)), where n is the initial array length, m is the number of add() calls, and k is the rank of the largest number to track. These bounds assume the heap is trimmed during initialization as described in Hint 4.
Hint 1
A brute force solution would involve sorting the array in every time a number is added using add(), and then returning the k-th largest element. This would take O(m * nlogn) time, where m is the number of calls to add() and n is the total number of elements added. However, do we really need to track all the elements added, given that we only need the k-th largest element? Maybe you should think of a data structure which can maintain only the top k largest elements.
Hint 2
We can use a Min-Heap, which stores elements and keeps the smallest element at its top. When we add an element to the Min-Heap, it takes O(log(k + 1)) time since we are storing at most k elements in it before the insertion. Retrieving the top element (the smallest in the heap) takes O(1) time. How can this be useful for finding the k-th largest element?
Hint 3
The k-th largest element is the smallest element among the top k largest elements. This means we only need to maintain k elements in our Min-Heap to efficiently determine the k-th largest element. Whenever the size of the Min-Heap exceeds k, we remove the smallest element by popping from the heap. How do you implement this?
Hint 4
Start with an empty Min-Heap. Insert each initial value and, after each insertion, remove the smallest element if the heap size exceeds k. This keeps initialization to O(nlog(k + 1)) time and O(k) space. Apply the same insert-and-trim steps for each add() call, then return the heap's smallest element, which is the k-th largest element.