Design a class to find the kth largest element in a stream.
This problem follows the Min-Heap of Size K pattern, commonly found in the Heap / Priority Queue category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Maintain a min-heap of size k. The root is always the kth largest.
A min-heap of size k keeps the k largest elements — the root (minimum of those k) is the kth largest overall.
class KthLargest:
def __init__(self, k, nums):
self.k = k
self.heap = nums[:k]
heapify(self.heap)
for num in nums[k:]:
if num > self.heap[0]:
heapreplace(self.heap, num)
def add(self, val):
if len(self.heap) < self.k:
heappush(self.heap, val)
elif val > self.heap[0]:
heapreplace(self.heap, val)
return self.heap[0]Practice Kth Largest Element in a Stream and similar Heap / Priority Queue problems with flashcards. Build pattern recognition through active recall.
Practice this problem