Kth Largest Element in a Stream

A heap gives you the smallest element of a collection in O(1) and lets you insert or remove in O(log n). Python's heapq module turns any list into a min-heap.

Design a class KthLargest that tracks the k-th largest element in a stream of numbers:

• KthLargest(k, nums) initialises the object with the integer k and an initial list nums (possibly empty).
• add(val) appends val to the stream and returns the k-th largest element seen so far.

It is guaranteed that there are at least k elements whenever add is called. Duplicates count separately: the 2nd largest of [5, 5, 1] is 5.

Examples

Input:
  KthLargest(3, [4, 5, 8, 2])
  add(3)  -> 4     stream so far: 2 3 4 5 8, 3rd largest is 4
  add(5)  -> 5     stream: 2 3 4 5 5 8
  add(10) -> 5
  add(9)  -> 8
  add(4)  -> 8
Output: [None, 4, 5, 5, 8, 8]

Constraints

• 1 <= k <= 1000
• 0 <= len(nums) <= 1000, and at most 1000 calls to add
• Re-sorting the whole stream on every add works, but a heap of size k is the intended O(log k) solution.

Goals

• Use heapq.heappush and heapq.heappop on a plain Python list
• Keep a min-heap of bounded size k so its smallest element is the k-th largest overall
• Maintain state across method calls in a class