Developers

Kth Largest Element in a Stream

EasyHeap and top-KAlso known as LeetCode 703

Design a class KthLargest. KthLargest(k, nums) creates it with the integer k and a starting list of numbers nums. add(val) adds the number val to the stream and returns the k-th largest number in the stream so far. The k-th largest is the k-th number when the numbers are sorted from largest to smallest, and repeated values count separately.

It is guaranteed that the stream has at least k numbers whenever add is called.

The tests only compare the values returned, so they cannot measure the time per call. A slower design may still pass them, but the problem asks for the stated complexity, so write that one.

Examples

Input KthLargest(3, [4, 5, 8, 2]), add(3), add(5), add(10), add(9), add(4)
Output [null, 4, 5, 5, 8, 8]
Input KthLargest(1, []), add(-3), add(-2), add(-4), add(0), add(4)
Output [null, -3, -2, -2, 0, 4]
With k = 1 the answer is the maximum so far.
Input KthLargest(2, [0]), add(-1), add(1), add(-2), add(-4), add(3)
Output [null, -1, 0, 0, 0, 1]

Constraints

  • 1 <= k <= 10,000
  • 0 <= nums.length <= 10,000
  • nums.length >= k - 1
  • -10,000 <= nums[i], val <= 10,000
  • At most 10,000 calls to add

Stuck? Take one hint at a time

Common mistakes
  • Using a max-heap of all the numbers and popping k - 1 times for every add, which is slow and destroys the heap.
  • Using a min-heap but never limiting its size to k, so the top is the overall minimum and not the k-th largest.
  • Popping when the new value is not larger than the top, so a small number evicts a good one.
  • Forgetting to process the starting numbers in the constructor with the same rule.
  • Reading the top before the heap holds k numbers. The starting numbers (at least k - 1) and the first add together fill it, so the guarantee covers this.
Questions an interviewer may ask next
  • The stream is huge and k is small. What is the memory use of the heap approach, and of the sorted list approach?
  • Numbers can also be removed from the stream. What data structure would you need? (A balanced tree with subtree sizes, or two heaps with lazy deletion.)
  • Support a query for any k, not only the one given at the start. (A balanced tree with subtree counts, or an order statistic tree.)
  • The values are small integers (here, 20,001 possible values). Can you do better than a heap? (A counting array and a pointer that only moves a little.)