Kth Largest in Stream
Class that, on each add(val), returns the k-th largest value seen so far.
02
Intuition
Persist the size-k min-heap between calls: its root IS the k-th largest at all times. add() pushes and trims — O(log k) per call, no re-sorting the stream.
03
Approach
1
Invariant across calls
Heap always holds the k largest so far; root = answer. Constructor seeds it from the initial array.
2
add = push + trim
Push val; if size > k pop the min. Return the root.
3
Why not sorted list
Insertion into a sorted structure is O(n); the heap's O(log k) wins for long streams.
04
Solution & live demo
python
▶1import heapq
▶2
▶3class KthLargest:
▶4 def __init__(self, k, nums):
▶5 self.k = k
▶6 self.heap = nums
▶7 heapq.heapify(self.heap)
▶8 while len(self.heap) > k:
▶9 heapq.heappop(self.heap)
▶10
▶11 def add(self, val):
▶12 heapq.heappush(self.heap, val)
▶13 if len(self.heap) > self.k:
▶14 heapq.heappop(self.heap)
▶15 return self.heap[0]
05
Edge cases
Fewer than k initial values
Heap fills up over the first adds; problem guarantees k values exist before queries matter.
Duplicates
Kept — k-th largest counts repeats.
06
Complexity
Time
O(log k) per add
Space
O(k)
Persistent top-k club.