Heaps Top K
406. Kth Largest Element in a Stream
Numbers arrive one at a time, and after each one you must report the k-th largest number seen so far.
Write a class KthLargest with a constructor and one method:
KthLargest(k, nums)storeskand the numbers that are already there,nums.add(val)adds the numberval, then returns thek-th largest of all the numbers so far,numsincluded.
The k-th largest number is the one in position k when all the numbers are sorted from largest to
smallest, counting from 1. Equal numbers take separate places.
Your class is tested on a new KthLargest(k, nums), which then gets one call add(values[i]) for each
number in values, in order. The answer is the list of what each call returns.
In C# and Go the method is Add. Go creates the object with Constructor(k, nums), and Rust with
KthLargest::new(k, nums).
Example 1
Input: k = 3, nums = [5, 1, 8, 3], values = [4, 9, 2, 6]
[4,5,5,6]Explanation: After 4 arrives, the numbers from largest to smallest are 8, 5, 4, 3, 1, so the third largest is 4. Then 9 pushes 5 into third place. 2 changes nothing near the top, and 6 takes third place after 9 and 8.
Example 2
Input: k = 1, nums = [], values = [-5, -10, 7, -1]
[-5,-5,7,7]Explanation: With k = 1 the answer is the largest number so far. nums can be empty here, because the first add
already brings one number.
Example 3
Input: k = 2, nums = [3], values = [3, 3, 1, 4]
[3,3,3,3]Explanation: nums holds one number, so the first add makes two. The 3s take separate places, so the second largest
stays 3, even after 4 arrives.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ k ≤ 1050 ≤ nums.length ≤ 105k − 1 ≤ nums.length, so every call toaddhas at leastknumbers to rank.1 ≤ values.length ≤ 105-109 ≤ nums[i], values[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.