Kth largest element in a stream

July 20, 2022


Problem URL: Kth largest element in a stream

We will create a min heap from the elements of the stream. We will make sure heap size is always k. That means the smallest element will ve at the heap's top and the largest element will be at the 0th index. Then we can return the 0th index of the heap in add operation.

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

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

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

Time Complexity: O(1) for each operation
Space Complexity: O(k) for k is the number of elements in the heap