Solution 1 - Min Heap (Size k)
Keep a min-heap of size k; top is the kth largest.
Keep a min-heap of size k; top is the kth largest.
""" 0703.1 - Kth Largest Element in a Stream - Solution 1 - Min Heap """
import heapq
from typing import List
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.h = nums
heapq.heapify(self.h)
while len(self.h) > k:
heapq.heappop(self.h)
def add(self, val: int) -> int:
heapq.heappush(self.h, val)
if len(self.h) > self.k:
heapq.heappop(self.h)
return self.h[0]