Kth Largest in Stream
Class that, on each add(val), returns the k-th largest value seen so far.
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.
Same min-heap-of-size-k idea as the static k-th largest, but now it has to survive repeated insertions. Capping the heap at k after every add means the root is permanently the answer, so each query is O(1) and each insert O(log k). Whenever a design question asks for a running order statistic, this is the structure.
Approach
Invariant across calls
Heap always holds the k largest so far; root = answer. Constructor seeds it from the initial array.
add = push + trim
Push val; if size > k pop the min. Return the root.
Why not sorted list
Insertion into a sorted structure is O(n); the heap's O(log k) wins for long streams.
Solution & live demo
Common pitfalls
Trimming the heap only in the constructor
def add(self, val):
heapq.heappush(self.heap, val)
return self.heap[0]heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap)
return self.heap[0]The heap grows past k and its root drifts down to the overall minimum, so the answer becomes the smallest value ever added rather than the k-th largest. The cap must be re-applied on every insertion.
Rejecting small values instead of pushing then popping
if val > self.heap[0]:
heapq.heapreplace(self.heap, val)
return self.heap[0]heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap)During warm-up the heap may hold fewer than k elements, and then even a small value belongs in it — the guard wrongly discards it and heap[0] crashes on an empty heap. Push-then-trim is correct in both phases.
Returning the largest element
return max(self.heap)
return self.heap[0]
The heap holds exactly the k largest values, so its smallest member is the k-th largest overall. Taking the maximum returns the single biggest element instead.
Edge cases
Heap fills up over the first adds; problem guarantees k values exist before queries matter.
Kept — k-th largest counts repeats.