Sponsored
Sponsored
Using a min-heap of size k can efficiently keep track of the kth largest element. This approach relies on the property of a heap where the smallest element (the root) in a min-heap can be accessed in constant time.
Steps:
Time Complexity: O(n log k) for initialization and O(log k) per add operation.
Space Complexity: O(k) for the heap.
1import heapq
2
3class KthLargest:
4 def __init__(self, k, nums):
5 self.k = k
6 self.min_heap = nums[:k]
7 heapq.heapify(self.min_heap)
8 for num in nums[k:]:
9 self.add(num)
10
11 def add(self, val):
12 if len(self.min_heap) < self.k:
13 heapq.heappush(self.min_heap, val)
14 elif val > self.min_heap[0]:
15 heapq.heapreplace(self.min_heap, val)
16 return self.min_heap[0]This implementation uses Python's heapq to manage a min-heap. The initial list of numbers is added to the heap, and then for each additional number, we determine whether it should replace the root of the heap, maintaining the heap size of k.
When a new value is added, if the heap is already full, it only adds the value if it is greater than the current minimum (root), ensuring that at the root is always the kth largest element.