'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List
import heapq


# optimized version
# keep it only having the k-largest elements by popping off small elements.
# With only k elements, the smallest item (self.pool[0]) will always be the
# kth largest.
class KthLargest1:
    # O(logK) for add and O(K) for the heap
    def __init__(self, k: int, nums: List[int]):
        self.nums = nums
        self.k = k
        heapq.heapify(self.nums)
        while len(self.nums) > k:
            heapq.heappop(self.nums)
        

    def add(self, val: int) -> int:
        if len(self.nums) < self.k: # 
            heapq.heappush(self.nums, val)
        elif val > self.nums[0]: # invisible condition: len(self.nums) == self.k
            heapq.heapreplace(self.nums, val)
        # print (self.nums)
        return self.nums[0]


# self-made, LTE, because I kept all the elements
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.nums = nums
        heapq.heapify(self.nums)
        self.k = k

    def add(self, val: int) -> int:
        heapq.heappush(self.nums, val)
        return heapq.nlargest(self.k, self.nums)[-1]