[link](https://leetcode.com/problems/kth-largest-element-in-a-stream/)

---

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

#### Example 1:

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

#### Constraints:

- 1 <= k <= 104
- 0 <= nums.length <= 104
- -104 <= nums[i] <= 104
- -104 <= val <= 104
- At most 104 calls will be made to add.
- It is guaranteed that there will be at least k elements - in the array when you search for the kth element.

---

The __init__ method is the class constructor that takes two parameters: k (the value of k) and nums (a list of integers). It initializes two instance variables: minHeap and k. The minHeap is initialized with the values from nums, and heapify is called to convert the list into a min-heap data structure. The while loop is used to maintain the heap property by repeatedly removing the smallest element from the heap until its size is reduced to k.

The add method takes an integer val as input and adds it to the minHeap using heappush. If the size of the minHeap exceeds k after adding the new value, the smallest element is removed using heappop. Finally, the method returns the smallest element in the minHeap, which represents the kth largest element.

#### Solution 1

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.minHeap, self.k = nums, k
        heapq.heapify(self.minHeap)
        while len(self.minHeap) > k:
            heapq.heappop(self.minHeap)


    def add(self, val: int) -> int:
        heapq.heappush(self.minHeap, val)
        if len(self.minHeap) > self.k:
            heapq.heappop(self.minHeap)
        
        return self.minHeap[0]
        

O(T): O(n log k)

The __init__ method takes O(n log k) time, where n is the length of the nums list. The heapify operation takes O(n) time, and the while loop performs k iterations, each taking O(log k) time due to the heappop operation.

The add method takes O(log k) time. The heappush operation takes O(log k) time, and if the size of the minHeap exceeds k, the heappop operation is performed, which also takes O(log k) time.

O(S): O(k)