minHeap: find Kth Largest Element in a Stream Python

PHOTO EMBED

Sat Aug 13 2022 21:49:52 GMT+0000 (Coordinated Universal Time)

Saved by @bryantirawan #python #leetcode #neetcode #stream #heap

class KthLargest:
	
    #Big O: n 
    def __init__(self, k: int, nums: List[int]): 
        #minHeap with k largest integers 
        
        self.minHeap, self.k = nums, k 
        heapq.heapify(self.minHeap) 
        
        while len(self.minHeap) > k: 
            heapq.heappop(self.minHeap) 
            
        

    #Big O: log N 
    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]
    

#Total big O: n log n 
    
    
    
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
content_copyCOPY

stream is basically an array that but new inputs can be constantly added

https://leetcode.com/problems/kth-largest-element-in-a-stream/