Kth Largest Element in a Stream
- 1 min read
- LC-Easy
- Binary-heap
3 years ago
Solution
-
Notice that for this problem, elements are never removed from the heap.
-
This means that our heap only needs to be of size
k -
It also needs to be a min heap- since we need the kth largest element. Which means in a heap of size
k, it is the smallest element -
Time
- To build heap: O(n + (n-k)log n)
- O(n) to build the heap, and O((n-k)log n) to pop excess elements out
- The add() function: O(log n) because all we're doing is popping one element out.
- To build heap: O(n + (n-k)log n)
-
Space: O(k) size of heap won't be more than k
def __init__(self, k: int, nums: List[int]):
self.heap = nums
self.k = k
heapify(self.heap)
while len(self.heap) > k:
heappop(self.heap)
def add(self, val: int) -> int:
heappush(self.heap, val)
if len(self.heap) > self.k:
heappop(self.heap)
return self.heap[0]