How do you find the kth largest element in a stream of numbers as they arrive?
You keep a heap that holds the k biggest values you have seen so far, and you use a min heap so that the smallest of them is easy to find and easy to throw away.
import heapq
class KthLargest:
def __init__(self, k):
self.k = k
self.heap = []
def add(self, value):
heapq.heappush(self.heap, value)
if len(self.heap) > self.k:
heapq.heappop(self.heap)
return self.heap[0] if len(self.heap) == self.k else None
So how does it work? Every new value goes into the heap. And then, if the heap has more than k items in it, you take the smallest one out. So the heap always holds the k biggest values that you have seen, and when there are fewer than k values it holds all of them.
And the answer is the front of the heap, which is the smallest of the k biggest values. That is exactly the kth largest of everything you have seen.
the values added the heap of size 3 the answer
------------------ ------------------ --------
5 [5] none yet
2 [2, 5] none yet
9 [2, 5, 9] 2
3 [3, 5, 9] 3
the heap is always the three biggest values it has seen
And the complexity is O of log k for the time of each add, and O of k for the space. And it does not matter how many values arrive, because the heap never grows past k.
And the answer is only available once you have k values, so the class gives back nothing until then. That is worth knowing about, because the question usually says that the add method gives back the kth largest and the stream is guaranteed to have enough values.
So the rule to remember is this. Keep the k biggest in a min heap and the front is the answer.
The next two questions in this topic show the plain loop and the version that skips the useless pushes.